LeetCode 946 验证栈序列

LeetCode 946 验证栈序列

给定 pushed 和 popped 两个数组,判断这两个数组能否通过一个空栈执行 push 和 pop 得到。

Solution 1: Greedy

用一个栈把 pushed 数组里的数依次 push 进去,push 之后检查栈顶的数是否等于 popped 的头元素,如果想等则去掉头元素。

class Solution {
public:
    bool validateStackSequences(vector<int> &pushed, vector<int> &popped) {
        stack<int> res;
        int i = 0, n = popped.size();
        for (auto &p:pushed) {
            res.push(p);
            while (!res.empty() && i < n && res.top() == popped[i]) {
                ++i;
                res.pop();
            }
        }
        return i == n;
    }
};
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        res = []
        i, n = 0, len(popped)
        for p in pushed:
            res.append(p)
            while res and i < n and res[-1] == popped[i]:
                i += 1
                res.pop()
        return i == n
comments powered by Disqus