剑指offer31:栈的压入、弹出(备忘)
借助一个辅助栈
自己写的
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
//借助一个辅助栈
stack<int> stk;
int len = pushed.size();
int idx_push = 0, idx_pop = 0;
while(idx_push < len){
while(idx_push < len && (empty(stk) ||
stk.top() != popped[idx_pop]))
stk.push(pushed[idx_push ++ ]);
while(!empty(stk) && stk.top() == popped[idx_pop]){
stk.pop();
idx_pop ++ ;
}
}
if(idx_pop == len)return true;
else return false;
}
};
大佬优化后的代码
class Solution{
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped){
int i = 0;
stack<int> stk;
for(auto x : pushed){
stk.push(x);
while(!empty(stk) && stk.top() == popped[i])
stk.pop(), i ++ ;
}
return empty(stk);
}
};