c++ - 判断出栈顺序是否合法。

Question

给定入栈顺序，判断出栈顺序是否合法？

要求：
空间复杂度O(1)
时间复杂度O(n)
 

网上提供的算法都是新建一个栈，空间复杂度为O(N),可不可以通过O(1)解决

Answer 1

Suppose your stack is a, b, c, d, e, with e at the bottom. Then there is an array that records the order of pushing onto the stack, such as [e, d, c, b, a], which means that e is pushed onto the stack first. At this time, just one variable is needed to store the stack capacity, which is initially 5.

When a pops off the stack, it is found that the variable stored in the variable is 5, so it is compared with the 5th bit of the array, and then the variable -1 becomes 4
When b is popped off the stack, it is found that the variable is stored in 4, and it is compared with the data The 4th bit is compared, and then the variable -1 becomes 3
...

Is this the space O(1) you want, or am I misunderstanding the question?

Answer 2

The question is wrong.

[Judge whether the pop sequence is legal] is equivalent to [Judge whether a man is a human being].

If a container is a stack, then it must be pushed and popped in order. Therefore, there is no question whether the order of popping the stack is legal or not.

---

In addition, you don’t need to comment. I know that the person who asked the question actually wanted to test all possibilities in the process of entering and exiting the stack. However, since the question does not reflect this need, the question is wrong.