31. stack push in and pop-up sequence

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)