Wie man eine Pop-Bestellung testet, ist legal oder nicht?

Da Ihre Push-Sequenz in aufsteigender Reihenfolge ist, wenn Sie eine Zahl N in Ihrer Pop-Warteschlange sehen, dann Alle Zahlen, die 1) unterhalb von N und 2) noch nicht gefüllt sind, müssen in absteigender Reihenfolge ausgegeben werden.

Zum Beispiel ist 4 3 5 1 2 keine gültige Reihenfolge, da, wenn wir "4" sehen, alle Zahlen auftauchen kleiner als '4', aber noch nicht gepoppt, muss in absteigender Reihenfolge gepoppt werden. Wenn Sie jedoch erst "1" und dann "2" drücken, wird diese Eigenschaft verletzt.

Eine Möglichkeit besteht darin, den Stack tatsächlich zu konstruieren:

Für jede Zahl X in der Pop-Reihenfolge:

• Wenn diese Nummer nicht mit der oberen des Stapels übereinstimmt (oder der Stapel leer ist), drücken Sie die Zahlen aus der Push-Reihenfolge, bis Sie X gedrückt haben. Wenn du alle Zahlen gedrückt hast und X nicht gefunden hast, gibt es keine Möglichkeit, die Pop-Reihenfolge zu erhalten.
• Pop X

Beachten Sie, dass dies tatsächlich nicht erfordert, dass die Push-Reihenfolge aufsteigend ist.

Sie können die Reihenfolge ausnutzen, um die oben genannten Punkte leicht zu optimieren (um früher zu versagen), indem Sie fehlschlagen, wenn X kleiner ist als die oberste des Stapels.

Da Sie jedes Element nur einmal drücken, ist das obige lineare Zeit (die Sie nicht besser können) und linearer Raum.

Beispiel:

Annahme: Die Push-Reihenfolge und Pop-Reihenfolge enthält genau die gleichen Zahlen. Wenn dies keine gültige Annahme ist, kann sie unter Verwendung eines Hash-Satzes (oder einer Hash-Map mit Zählungen, falls es Duplikate geben kann) in linearer Zeit validiert werden, obwohl dies die O (1) -Raumkomplexität beeinträchtigen würde.

Idee: Jedes Element in der Pop-Reihenfolge muss entweder kleiner als das Element davor oder mehr als das Maximum sein, sonst ist die Pop-Reihenfolge nicht gültig.

Dies kann in O (n) Zeit und O (1) Abstand überprüft werden, indem nur das Maximum verfolgt wird.

Warum das funktioniert:

Die Push-Reihenfolge ist in aufsteigender Reihenfolge, also unabhängig davon, wann Sie Elemente poppen:

1. Der Stapel wird auch immer in aufsteigender Reihenfolge und
sein
2. Das nächste Element in der Push-Reihenfolge ist immer größer als das größte Element auf dem Stapel.

Also gibt es zwei Möglichkeiten:

• Zwei Pop-Operationen in einer Reihe - in diesem Fall ist das zweite Element kleiner
• Zwei Pop-Operationen mit einer oder mehreren Push-Operationen dazwischen - in diesem Fall ist das zweite Element größer als das Maximum (nach 2).

Beispiele:

4 5 3 2 1 ist gültig seit 5 & gt; max (4), 3 & lt; 5, 2 & lt; 3 und 1 & lt; 2.

4 3 5 1 2 ist nicht gültig seit 2 & gt; 1 aber 2 & lt; max (5).

1 2 3 5 4 ist gültig seit 2 & gt; max (1), 3 & gt; max (2), 5 & gt; max (3) und 4 & lt; 5.

Lösung:

Beispiel 1: {1, 2, 4, 3}, legale Reihenfolge

Beispiel 2: {1, 4, 2, 3}, illegale Sequenz

Ich versuche mein Bestes, um meine Idee zu erklären, hoffe, dass ich die Dinge klar gemacht habe.