剑指 Offer 31. 栈的压入、弹出序列

原题

剑指 Offer 31. 栈的压入、弹出序列

思路

借助一个辅助栈，来模拟序列的压入压出。
压入压出的特点就是 在过程中可以压入再接着压出。
所以我们每向辅助栈压入一个元素，就判断目前popped序列的元素与栈顶元素是否相等，相等就pop，同时序列指向下一个元素，继续判断，直至不相等或者栈为空。 当所有的push序列都压入之后，遍历也结束，如果辅助栈为空，则表示压出序列是正确的

代码

class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
int j = 0, n = pushed.size();
stack st;
for (int i = 0; i < n; i++) {
st.push(pushed[i]);
while (!st.empty() && st.top() == popped[j]) {
j++;
st.pop();
}
}
return st.empty();
}
};

运行截图

收获

像这种模拟题要抓住过程中最大的特点来写