946. Validate Stack Sequences

Description

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Solution

比较直接的做法：实际进行入栈和退栈操作，严格按照入栈序列入栈，尝试匹配出栈序列，成功匹配则退栈，若已无元素可入栈切退栈序列未匹配完成，则序列不合法。

Code

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