LeetCode 946. 验证栈序列

约 4 分钟
文章信息 14 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 微软 美团 快手 百度 小米 商汤 旷视 小红书
标签
数组 栈 模拟 栈经典题
目录

题目描述

✅ 946. 验证栈序列

image-20230312180033626

题意分析

题目给两个长度相同的序列。pushed 规定元素进入容器的先后顺序，这个顺序不能打乱；popped 是声称的离开顺序。要回答的是一个判定问题：存在不存在一种「进」和「出」的交错方式，使得元素恰好按 popped 的顺序离开。容器的规则由题目写死：后进先出，只能看到、只能取走最后放进去的那个。

约束里有两个信号值得注意。第一，pushed 和 popped 互为排列且元素互不相同，所以不用担心重复值造成的歧义，每个数值唯一对应一个位置。第二，长度上限只有 $1000$，看起来什么都能过，但指数级的枚举仍然会爆炸，所以规模小并不等于可以搜索。

边界要想清楚三种：长度为 $1$，此时必然合法；popped 与 pushed 完全相同，对应「压一个立刻弹一个」；popped 与 pushed 完全相反，对应「全部压完再全部弹出」。这三种都应该返回 true，可以拿来当自检用例。

解法：栈模拟入栈出栈

核心思路

按 pushed 顺序模拟真实入栈过程，并用指针 j 指向 popped 中下一个应出栈的元素。每压入一个元素后，只要栈顶等于 popped[j]，就持续弹栈并推进 j。

“能弹就立刻弹”是安全的：栈顶若已是下一个目标却不弹，之后压入的元素会挡在它上方，而这些元素又不能先于目标弹出，因此延迟不会产生新的合法方案。栈顶不匹配时则只能继续入栈，操作没有分支。

不变量是：每轮匹配结束后，栈中恰好保存已入栈但尚未按 popped 消费的元素，j 等于已经完成的出栈次数。最终 j == popped.length 当且仅当整个出栈序列可实现。

解题步骤

  • 创建空栈，并令 j = 0。
  • 依次将 pushed 中的元素压栈。
  • 每次压栈后，用 while 连续弹出所有与 popped[j] 匹配的栈顶元素，并递增 j。
  • 遍历结束后，判断 j 是否走到 popped 末尾。

对 pushed = [1,2,3,4,5]、popped = [4,5,3,2,1]，压入 $4$ 后弹出 $4$；压入 $5$ 后会连续弹出 $5,3,2,1$，最终 j = 5，返回 true。若 popped = [4,3,5,1,2]，弹出 $5$ 后栈顶是 $2$，无法先弹出 $1$，最终返回 false。

代码实现

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int j = 0;
        for (int value : pushed) {
            stack.push(value);
            while (!stack.isEmpty() && j < popped.length && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return j == popped.length;
    }
}

func validateStackSequences(pushed []int, popped []int) bool {
    stack := make([]int, 0)
    j := 0
    for _, value := range pushed {
        stack = append(stack, value)
        for len(stack) > 0 && j < len(popped) && stack[len(stack)-1] == popped[j] {
            stack = stack[:len(stack)-1]
            j++
        }
    }
    return j == len(popped)
}

复杂度分析

  • 时间复杂度：$O(n)$，每个元素最多入栈、出栈各一次。
  • 空间复杂度：$O(n)$，模拟栈最坏保存全部元素。

关键点总结

  • j 始终表示下一个待匹配的出栈位置，也是最终的成功判据。
  • 一次入栈可能解锁多个出栈动作，所以必须使用 while。
  • 贪心正确性的关键是：下一个目标已在栈顶时，延迟弹出不可能更优。
  • 内层循环虽嵌套，但每个元素只会弹出一次，总复杂度仍为 $O(n)$。

易错点总结

  • 用 if 代替 while：一次只弹一个元素，会漏掉连续可弹出的栈顶。
  • 不检查栈是否为空就读取栈顶：合法序列清空栈后会发生异常。
  • 漏掉 j < popped.length：匹配完成后继续读取 popped[j] 可能越界。
  • 栈顶暂时不匹配就返回 false：此时仍可能通过继续入栈得到目标元素。
  • 只判断两个数组互为排列：排列相同不代表满足后进先出的约束，例如 [3,1,2] 不是 [1,2,3] 的合法出栈序列。

相似题目

题目 难度 考察点
剑指 Offer 31. 栈的压入、弹出序列 中等 同题的出入栈模拟
20. 有效的括号 简单 栈判定配对合法性
155. 最小栈 中等 栈的辅助信息维护
739. 每日温度 中等 单调栈求下一个更大
剑指 Offer 09. 用两个栈实现队列 简单 双栈模拟队列顺序