8

2 つの一意の数列 と が与えられpush order of stackた場合pop order of stack、 の数字はpush order昇順で並べ替えられているため、pop orderが合法かどうかを尋ねます。

たとえば、push orderは 1 2 3 4 5 であるため、4 5 3 2 1 は有効なポップ注文です。これは、次のようにプッシュおよびポップできるためです。

push 1, push 2, push 3, push 4, pop, push 5, pop, pop, pop, pop

したがって、ポップ オーダー: 4 5 3 2 1 は正当であり、4 3 5 1 2 は正当なポップ オーダーではありません。

4

4 に答える 4

4

プッシュ シーケンスは昇順であるため、Nポップ キューに数字が表示された場合、1) 下Nにあり、2) まだポップされていないすべての数字を降順でポップする必要があります。

たとえば、4 3 5 1 2 は有効な順序ではありません。'4' がポップされた場合、'4' より小さいが、まだポップされていないすべての数値を降順でポップする必要があるためです。ただし、最初に '1' をポップしてから '2' をポップすると、このプロパティに違反します。

于 2013-07-24T00:06:49.297 に答える
3

1 つのオプションは、実際にスタックを構築することです。

Xポップ順の各番号について:

  • この番号がスタックの一番上と同じでない場合 (またはスタックが空である場合)、プッシュするまで番号をプッシュ順序からプッシュしますX。すべての番号をプッシュしても が見つからなかった場合X、ポップ オーダーを取得する方法はありません。
  • ポップX

実際には、プッシュ順序が昇順である必要はないことに注意してください。

X順序付けを利用して、 がスタックの最上位より小さい場合に失敗することで、上記をわずかに最適化する (より早く失敗する) ことができます。

各要素を最大で 1 回プッシュするだけなので、上記は線形時間 (これ以上のことはできません) と線形空間です。

例：

Push: 1 2 3 4 5  
Pop: 4 5 3 2 1

Processing: 4
    Stack empty -> push until 4 is on the top of the stack.
    Stack: 1 2 3 4
    Pop 4
    Stack: 1 2 3

Processing: 5
    3 != 5 -> push until 5 is on the top of the stack.
    Stack: 1 2 3 5
    Pop 5
    Stack: 1 2 3

Processing: 3
    Pop 3
    Stack: 1 2

Processing: 2
    Pop 2
    Stack: 1

Processing: 1
    Pop 1
    Stack: 

Done.
于 2013-07-24T08:03:14.230 に答える
2

仮定:プッシュ注文とポップ注文にはまったく同じ数字が含まれています。これが有効な仮定でない場合は、O(1) 空間の複雑さを損なう可能性がありますが、線形時間でハッシュ セット (または重複がある場合はカウント付きのハッシュ マップ) を使用して検証できます。

アイデア:ポップ順のすべての要素は、その前の要素よりも小さいか、それまでの最大値よりも大きい必要があります。そうでない場合、ポップ順は無効です。

これは、最大値を追跡するだけで、O(n) 時間と O(1) 空間でチェックできます。

これが機能する理由:

プッシュ順序は昇順であるため、要素をいつポップするかに関係なく、次のようになります。

  1. スタックも常に昇順であり、
  2. プッシュ順序の次のアイテムは、スタックにある最大の要素より常に大きくなります。

したがって、次の 2 つのオプションがあります。

  • 連続する 2 つの pop 操作 - この場合、2 番目の要素は小さくなります。
  • 間に 1 つ以上のプッシュ操作がある 2 つの pop 操作 - この場合、2 番目の要素は最大値よりも大きくなります (2 に続く)。

例:

4 5 3 2 1は 5 > max (4)、3 < 5、2 < 3、および 1 < 2 であるため有効です。

4 3 5 1 2は 2 > 1 であるが 2 < max (5) であるため有効ではありません。

1 2 3 5 4は 2 > max (1)、3 > max (2)、5 > max (3)、および 4 < 5 であるため有効です。

于 2013-07-24T09:54:41.110 に答える