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

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

題目錯了。

【判斷出棧順序是否合法】等同於【判斷男人是不是人】。

如果一個容器是棧，那麼它一定是按照順序入棧出棧的。所以不存在出棧順序合不合法一說。

---

另外你們不需要評論，我知道出題人的意思其實是想考入棧出棧這個過程中的所有可能，但由於題目並沒有體現出這個需求，因此題目是錯的。