946. 验证栈序列
模拟 class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { int n = popped.size(); stack<int> stPop,stPush; for(int i=n-1;i>=0;i--) stPop.push(popped[i]); for(int i=0;i<n;i++){ stPush.push(pushed[i]); while(!stPush.empty() && stPop.top()==stPush.top()){ stPop.pop(); stPush.pop(); } } while(!stPop.empty()){ if(stPop.top()!=stPush.top()) return false; stPop.pop(); stPush.pop(); } return true; } }; 贪心 假设当前栈顶元素值为 2，同时对应的 popped 序列中下一个要 pop 的值也为 2，那就必须立刻把这个值 pop 出来。因为之后的 push 都会让栈顶元素变成不同于 2 的其他值，这样再 pop 出来的数 popped 序列就不对应了。 class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { int n = pushed.size(), j = 0; stack<int> s; for(int x:pushed){ s.push(x); while(!s.empty() && j<n && s.top()==popped[j]){ j++; s.pop(); } } return j==n; } };