[系列文章] leetcode 每日一题946

发布于 24 天前  85 次阅读


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;
    }
};

一只在互联网躬耕的菜鸟,写代码是热爱,二次元也是,mikoto也是