判断出栈顺序是否合法。

Question

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

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

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

Answer 1

假设你的栈是a, b, c, d, e，e在最底。然后有个数组记载着入栈顺序，比如[e, d, c, b, a]，意味着e第一入栈的。这时只要一个变量来存栈的容量就行了吧，初始是5。

当a出栈，发现变量里面存的是5，就和数组第5位对比，然后变量-1变成4
当b出栈，发现变量里面存的是4，就和数据第4位对比，然后变量-1变成3
...

这是不是你想要的空间O(1)，还是我对题目理解有误？

Answer 2

题目错了。

【判断出栈顺序是否合法】等同于【判断男人是不是人】。

如果一个容器是栈，那么它一定是按照顺序入栈出栈的。所以不存在出栈顺序合不合法一说。

---

另外你们不需要评论，我知道出题人的意思其实是想考入栈出栈这个过程中的所有可能，但由于题目并没有体现出这个需求，因此题目是错的。