67-验证栈序列

自己的做法

算法思想

使用一个栈nums，遍历pushed队列，将元素入栈，使用一个指针指向popped序列的第一个待验证元素，并判断栈顶元素是否和该待验证元素相等，如果相等，就出栈，并将待验证指针后移一个，继续判断，直到栈为空，或待验证指针为空，或两元素不相等。

最后判断nums栈是否 为空，如果为空，证明栈序列正确，否则错误。

算法实现

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> nums;
        int n = popped.size();
        //待验证元素指针
        int j = 0;
        for(int i = 0; i < pushed.size(); i++) {
            nums.push(pushed[i]);
            while (!nums.empty() && j < n && nums.top() == popped[j]) {
                nums.pop();
                j++;
            }

        }
        return nums.empty();
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(n)$。

参考做法相同。

只不过在返回值处的语句是j == n。意思一样。