946. Validate Stack Sequences.md

946. Validate Stack Sequences

思路

输入两个整数序列，第一个序列表示栈的入栈顺序，请判断第二个序列是否可能为该栈的出栈顺序。

思路一

例

pushed = [1,2,3,4,5]
popped = [4,5,3,2,1]

出栈序列第一个是4，我们要什么时候pop出4呢，很明显是当4第一次出现在栈顶的时候（即push了4就要立马pop出），否则为了pop出4需要先pop出在4上面的元素，不符合出栈序列要求。出栈序列后面的元素同理，即是一个贪心的过程: 从前往后依次将元素入栈，在这个过程中不断判断栈顶元素是否为下一个popped元素，若是则应该出栈。最后如果栈为空则说明全部出栈了，返回真；否则返回假。

时空复杂度均为O(n)

思路二

一开始想到的是暴力法，即模拟出入栈的过程，用DFS回溯。亲测比思路一慢很多很多，就不细说了。

C++

思路一

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int n = pushed.size(), pop_i = 0;
        stack<int>stk;
        for(int i = 0; i < n; i++){
            stk.push(pushed[i]);
            while(!stk.empty() && stk.top() == popped[pop_i]){
                stk.pop();
                pop_i++;
            }
        }
        return stk.empty();
    }
};

思路二

class Solution {
private:
    vector<int>pushed_, popped_;
    int n;
    bool helper(stack<int>&stk, int push_i, int pop_i){
        if(pop_i == n) return true;
        
        // 出栈
        if(!stk.empty() && stk.top() == popped_[pop_i]){ 
            int tmp = stk.top(); stk.pop();
            if(helper(stk, push_i, pop_i + 1)) return true;
            stk.push(tmp);
        }
        
        // 入栈
        if(push_i >= n) return false;
        stk.push(pushed_[push_i]);
        if(helper(stk, push_i + 1, pop_i)) return true;
        
        return false;
    }
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        pushed_ = pushed;
        popped_ = popped;
        n = pushed.size();
        if(n <= 1) return true;
        stack<int>stk, out;
        int i = 0;
        return helper(stk, 0, 0);
    }
};