LeetCode 剑指 Offer 31. 栈的压入、弹出序列

约 5 分钟
文章信息 13 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 微软 美团 阿里巴巴 网易 虾皮 剑指 Offer 剑指 Offer（第 2 版）
标签
数组 栈 模拟
目录

题目描述

✅ 剑指 Offer 31. 栈的压入、弹出序列

image-20241107205614060

题意分析

给定两个长度相同、元素互不相同的序列 pushed 和 popped，popped 是 pushed 的一个排列。问：对一个初始为空的容器，按 pushed 给定的先后顺序放入元素，能否恰好按 popped 给定的先后顺序把元素取出。能则返回 true，否则返回 false。

题目给的是一个「后进先出」的容器：任何时刻只能取出最后放进去的那个元素。这条约束是全部难度的来源——放入的顺序被 pushed 写死了，我们唯一能决定的自由度只有「什么时候取」：每一步要么再放一个进去，要么把当前最上面的那个取出来。

约束信号：两个序列长度相同且互为排列，说明每个元素恰好放入一次、取出一次，总操作数固定为 2n；元素互不相同，说明「当前最上面的元素是否就是下一个要取的」这个判断没有歧义。长度上限只有 1000，规模很小，可以放心地把整个过程原样跑一遍。

边界情况：两个序列都为空时应返回 true；popped 与 pushed 完全相同（每放一个立刻取一个）；popped 与 pushed 完全相反（全部放完再依次取出）；以及某个需要取出的元素被压在别的元素下面导致永远取不到。

解法：辅助栈模拟

核心思路

压栈顺序已经由 pushed 固定，唯一需要判断的是每个元素应在何时弹出。用辅助栈重放过程：依次压入元素，每次压入后，只要栈顶等于 popped 中下一个待弹出的值，就连续弹出。

这个策略没有遗漏其他可能：栈顶若等于下一个目标，现在就必须弹出；如果继续压入，新元素会挡在它上面，却又必须在目标元素之后弹出，产生矛盾。栈顶若不等于目标，则当前不能弹，只能继续压入。

不变量：指针 j 之前的元素已按 popped 顺序弹出；辅助栈自底向上保存所有已压入但尚未弹出的元素。模拟结束时，j == popped.length 当且仅当整个出栈序列可实现。

解题步骤

  • 创建空栈，令 j = 0 指向下一个待匹配的出栈元素。
  • 按顺序遍历 pushed，将当前元素压栈。
  • 当栈非空且栈顶等于 popped[j] 时，弹出栈顶并令 j++；必须用 while 处理连续弹出。
  • 所有元素压入完成后，判断 j 是否到达 popped 末尾。

例如 pushed = [1,2,3,4,5]、popped = [4,5,3,2,1]：压入 4 后弹出 4；压入 5 后会连续弹出 5、3、2、1，最终全部匹配，返回 true。

代码实现

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, len(pushed))
    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)$。每个元素最多压栈一次、弹栈一次，内层循环的总次数不超过 $n$。
  • 空间复杂度：$O(n)$，辅助栈最坏保存全部元素。

关键点总结

  • “匹配就立即弹出”是由目标顺序强制决定的，不是需要比较收益的贪心选择。
  • 一次压栈可能触发多次弹栈，因此使用 while 而不是 if。
  • j 表示已成功匹配的出栈元素个数，最终用它判断序列是否合法。
  • Java 的 push / peek / pop 要成套使用，避免误用队列方向。

易错点总结

  • 内层只写 if：会漏掉一次压栈后连续弹出多个元素的情况。
  • 先把所有元素压栈再比较：合法序列可能要求压入过程中穿插弹出，会被误判。
  • 忘记检查栈为空或 j 越界：继续读取栈顶或 popped[j] 会抛异常。
  • 弹栈后忘记 j++：匹配进度不会前进，后续判断全部错误。
  • 混用 addLast 与 peekFirst：会把栈模拟成队列，破坏后进先出顺序。

相似题目

题目 难度 考察点
946. 验证栈序列 中等 与本题完全同题，可直接复用同一份模拟代码
20. 有效的括号 简单 栈顶配对即弹，考的是匹配规则而非出栈时机
剑指 Offer 30. 包含min函数的栈 简单 辅助栈同步维护历史最小值，考数据结构设计
剑指 Offer 09. 用两个栈实现队列 简单 双栈倒腾把后进先出改造成先进先出，复杂度靠摊还分析
150. 逆波兰表达式求值 中等 遇操作数入栈、遇运算符弹两个，栈承载的是中间结果
71. 简化路径 中等 用栈处理 .. 回退，难点在分段与边界规则
剑指 Offer 33. 二叉搜索树的后序遍历序列 中等 同为序列合法性判定，改用递归分治或单调栈