当前位置:网站首页>31. stack push in and pop-up sequence

31. stack push in and pop-up sequence

2022-06-12 05:18:00 Be your goat

The finger of the sword Offer 31. Pressure into the stack 、 Pop-up sequence

Ideas : Stack simulation

  • initialization : Auxiliary stack stack, Pop up the index of the sequence i
  • Traverse the stack sequence , Each element is marked as num:
    • Elements num Push ;
    • Loop out the stack : if stack Top element of = Pop up sequence elements popped[i], Perform stack out and i++
  • Return value : if stack It's empty , Then this pop-up sequence is legal
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stk;
        int i=0;
        for(int n:pushed){
            stk.push(n);
            while(stk.size()&&stk.top()==popped[i]){
                stk.pop();
                ++i;
            }
        }
        return stk.empty();
    }
};

Time complexity O(n)

Spatial complexity O(n)

原网站

版权声明
本文为[Be your goat]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/03/202203010618459140.html

随机推荐