栈的压入、弹出序列
栈的压入、弹出序列
http://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106
描述
这是针对初学者的题解。
知识点:栈
难度:一星
题解
题目抽象:给出一个入栈序列pushV和出栈序列popV, 判断出栈序列是否满足条件。
方法:模拟法
直接模拟即可。因为弹出之前的值都会先入栈,所以这里用个栈来辅助。
- 初始化:用指针i指向pushV的第一个位置, 指针j指向popV的第一个位置
- 如果pushV[i] != popV[j], 那么应该将pushV[i]放入栈中, ++i
- 否则,pushV[i]==popV[j], 说明这个元素是放入栈中立马弹出,所以,++i, ++j,然后应该检查popV[j]
与栈顶元素是否相等,如果相等,++j, 并且弹出栈顶元素
4,重复2,3, 如果i==pushV.size(), 说明入栈序列访问完,此时检查栈是否为空,如果为空,说明匹配,斗则不匹配。
如下图:
![图片说明](https://uploadfiles.nowcoder.com/images/20200419/284295_1587300920579_C29DD1A7B53A19CC1A8C1045C55DDF65 "图片标题")
代码如下:
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { stack<int> st; int i = 0, j = 0; while (i < pushV.size()) { if (pushV[i] != popV[j]) { st.push(pushV[i++]); } else { ++i, ++j; while (!st.empty() && st.top() == popV[j]) { st.pop(); ++j; } } } // end outer while return st.empty(); } };
时间复杂度:O(n)
空间复杂度:O(n), 用了一个辅助栈,最坏情况下会全部入栈