946. Validate Stack Sequences

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int n = pushed.size(), i=0, j=0;
        stack<int> sta;
        while(i<n && j<n){
            if(pushed[i] == popped[j]){i++;j++;}
            else sta.push(pushed[i++]);
            // 檢查當前j 指向的值是否為stack.top()
            while(j<n && !sta.empty() &&  sta.top() == popped[j]){
                sta.pop();
                j++;
            }
        }
        return j==n && sta.empty();
    }
};

analysis

  • time complexity O(n)
  • space complexity O(n)