We take the sequence of integers from $1$ to $n$, and we push them onto a stack one by one in order. Between each push, we can choose to pop any number of items from the stack (from 0 to the current stack size).
Every time we pop a value from the stack, we will print it out.
For example, $1,2,3$ is printed out when we do push, pop, push, pop, push, pop
. $3,2,1$ comes from push, push, push, pop, pop, pop
.
However, $3,1,2$ is not a possible printout, because it is not possible to have $3$ printed followed by $1$, without seeing $2$ in between.
Question: How can we detect impossible orders like $3,1,2$?
In fact, based on my observation, I have come out a potential solution. But the problem is I can't prove my observation is complete.
The program that I wrote with the following logic:
When the current value minus the next value is larger than 1, a value between current and next cannot appear after next. For example, if current=3 and next=1, then the value between current (3) and next (1) is 2 which cannot appear after next(1), hence $3,1,2$ violates the rule.
Does this cover all cases?