leetcode：946. 验证栈序列

题目

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

示例：

  1. 输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
  2. 输出：true
  3. 解释：我们可以按以下顺序执行：
  4. push(1), push(2), push(3), push(4), pop() -> 4,
  5. push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

解答 & 代码

直接用栈模拟

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.size() != popped.size())
            return false;
        int len = pushed.size();
        stack<int> s;        // 栈
        int idxPop = 0;
        // 遍历 pushed 序列
        for(int i = 0; i < len; ++i)
        {
            // 将当前数 push 到栈中
            s.push(pushed[i]);
            // 检查栈顶元素是否要弹出
            while(!s.empty() && s.top() == popped[idxPop])
            {
                s.pop();
                ++idxPop;
            }
        }
        // 如果 pushed 序列以全部存入栈，但是栈最终不为空，即没有全部弹出，则返回 false，否则返回 true
        return s.empty();
    }
};

复杂度分析：设序列长为 n

  • 时间复杂度 O(n)：
  • 空间复杂度 O(n)：

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 71.95% 的用户
内存消耗：14.8 MB, 在所有 C++ 提交中击败了 86.76% 的用户