Algorithmen und Datenstrukturen

Prüfe, ob ein Array stack-sortierbar ist

Gegeben sind die Zahlen 1, 2, 3, ..., n in einem Array in beliebiger Reihenfolge. Die Aufgabe besteht darin zu ermitteln, ob das gegebene Array stack-sortierbar ist. Ein Array A ist dann stack-sortierbar, wenn es mithilfe eines Hilfsstapels möglich ist, ein Array B zu erzeugen, das am Ende des Ablaufs in aufsteigender Reihenfolge sortiert ist. Die erlaubten Operationen sind:
  1. Den ersten Wert aus A entnehmen und oben auf den Stapel legen.
  1. Das oberste Element vom Stapel nehmen und hinten an B anhängen.
Wenn B am Ende in aufsteigender Reihenfolge sortiert ist, gilt A als stack-sortierbar.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (1 ≤ n ≤ ).
In der nächsten Zeile stehen n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ n).

Ausgabe

Das Programm soll Yes ausgeben, wenn A stack-sortierbar ist, andernfalls No.

Beispiele

Eingabe
Ausgabe
4 4 1 2 3
Yes
3 3 2 1
Yes
3 1 2 3
Yes
4 2 4 1 3
No

Erklärung

A = [4, 1, 2, 3], S = [], B = []
  1. Operation 1: A = [1, 2, 3], S = [4], B = []
  1. Operation 1: A = [2, 3], S = [4, 1], B = []
  1. Operation 2: A = [2, 3], S = [4], B = [1]
  1. Operation 1: A = [3], S = [4, 2], B = [1]
  1. Operation 2: A = [3], S = [4], B = [1, 2]
  1. Operation 1: A = [], S = [4, 3], B = [1, 2]
  1. Operation 2: A = [], S = [4], B = [1, 2, 3]
  1. Operation 2: A = [], S = [], B = [1, 2, 3, 4]
A = [3, 2, 1], S = [], B = []
  1. Operation 1: A = [2, 1], S = [3], B = []
  1. Operation 1: A = [1], S = [3, 2], B = []
  1. Operation 1: A = [], S = [3, 2, 1], B = []
  1. Operation 2: A = [], S = [3, 2], B = [1]
  1. Operation 2: A = [], S = [3], B = [1, 2]
  1. Operation 2: A = [], S = [], B = [1, 2, 3]
A = [1, 2, 3], S = [], B = []
  1. Operation 1: A = [2, 3], S = [1], B = []
  1. Operation 2: A = [2, 3], S = [], B = [1]
  1. Operation 1: A = [3], S = [2], B = [1]
  1. Operation 2: A = [3], S = [], B = [1, 2]
  1. Operation 1: A = [], S = [3], B = [1, 2]
  1. Operation 2: A = [], S = [], B = [1, 2, 3]
Es ist unmöglich, das Array [2, 4, 1, 3] zu stack-sortieren
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue