Leetcode题解 剑指 Offer 31. 栈的压入、弹出序列

PROBLEM

剑指 Offer 31. 栈的压入、弹出序列

难度 中等

MY ANSWER

使用栈进行模拟，时间复杂度为O(n)，空间复杂度为O(n)。

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int pushp = 0, popp = 0;
        stack<int> s;
        while(pushp < pushed.size() || popp < popped.size()) {
            if(s.empty() || pushed.size() && popped[popp] != s.top()) {
                while(pushp < pushed.size()) {
                    s.push(pushed[pushp]);
                    if(pushed[pushp] == popped[popp]) {
                        pushp++;
                        break;
                    }
                    pushp++;
                }
            }
            if(s.size() && popped[popp] == s.top()) {
                s.pop();
                popp++;
            }
            else {
                return false;
            }
        }
        return true;
    }
};

BETTER SOLUTION

代码更简洁的模拟，当栈不为空时说明序列不对。使用c++11的foreach：for(int num:pushed)。时间空间复杂度相同。

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int>st;
        int i=0;
        //用栈模拟 pushed[i]==4的时候，弹出 i++, 5 的时候也弹出,i++, 这时候栈顶是3 还是相同操作，很巧妙
        for(int num:pushed){
            // 1 2 3 4 5      4 5 3 2 1
            st.push(num);
            while(!st.empty()&&st.top()==popped[i]){
                st.pop();
                i++;
            }
        }
        return st.empty();
    }
};

SUMMARY

加深对栈的理解，使用foreach以及合并条件判断简化代码。