剑指 Offer 31 栈的压入、弹出序列:用模拟栈判定弹出顺序的完整实现与复杂度分析

本文基于 CS-Notes 仓库中的剑指 Offer 题解文档 31. 栈的压入、弹出序列 展开,完整覆盖原题描述、"模拟压入弹出"的解题思路与标准 Java 解法,并补充题目关键假设的解读、两个样例的逐步推演、复杂度分析、边界条件处理以及与仓库内栈数据结构实现的关联,帮助读者彻底掌握这道经典栈模拟题的写法与易错点。

题目描述

原题完整表述(来自文档):

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

例如序列 1,2,3,4,5 是某栈的压入顺序,序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列,但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。

这道题的核心是判定可行性,而不是输出具体操作:给定压入序列 pushSequence,问 popSequence 是否恰好是某种合法出入栈操作下得到的弹出结果。

题目中"压入栈的所有数字均不相等"这一假设非常关键:它保证了 popSequence 中的每个元素在 pushSequence 里至多出现一次,使得模拟过程中"当前期望弹出的值"唯一明确。若允许重复数字,匹配会变得多义,判定逻辑需要额外处理,这也是为什么题目要提前给出这个前提。

解题思路:用栈模拟压入弹出

文档给出的思路是:使用一个栈来模拟压入弹出操作。每次入栈一个元素后,都要判断一下栈顶元素是不是当前出栈序列 popSequence 的第一个元素,如果是的话则执行出栈操作并将 popSequence 往后移一位,继续进行判断。

这句话拆解成三步:

1. 按顺序压入:外层循环按 pushSequence 的下标依次 push,不能乱序,因为压入顺序是题目给定的;
2. 能弹就弹:每压入一个元素后,用 while 循环持续检查栈顶是否等于 popSequence[popIndex],相等就弹出并把弹出游标 popIndex 前移,直到栈顶不再匹配或栈已空;
3. 全部结束后判空:所有元素处理完后,若栈为空说明所有元素都被合法弹出,返回 true;否则说明有元素"卡"在栈里弹不出去,返回 false。

这个贪心策略之所以正确,是因为栈的弹出操作具有唯一强制性:在任意时刻,只有"弹栈顶"一种选择,不存在分支决策。因此只要按"栈顶匹配就立刻弹"地模拟,得到的就是该压入序列下唯一确定的弹出过程,最终栈是否为空即判定结果。

标准 Java 解法

完整继承文档中的实现:

public boolean IsPopOrder(int[] pushSequence, int[] popSequence) {
    int n = pushSequence.length;
    Stack<Integer> stack = new Stack<>();
    for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {
        stack.push(pushSequence[pushIndex]);
        while (popIndex < n && !stack.isEmpty()
                && stack.peek() == popSequence[popIndex]) {
            stack.pop();
            popIndex++;
        }
    }
    return stack.isEmpty();
}

几个值得注意的实现细节:

• 双下标 pushIndex / popIndex 分别代表"下一个待压入元素"和"当前期望弹出元素",整个模拟过程是单趟扫描,不需要回溯;
• stack.peek() == popSequence[popIndex] 这一比较是安全的:popSequence 是 int[],popSequence[popIndex] 为基本类型 int,而 peek() 返回的 Integer 会因比较对象是 int 而自动拆箱,最终是比较两个 int 值,不存在 Integer 缓存区间导致引用比较的坑;
• while 循环中 popIndex < n 放在最前面,防止弹出序列已全部消费完后越界访问;
• 方法最后 return stack.isEmpty(),等价于"所有元素都被弹出"。

样例推演:为什么 4,5,3,2,1 合法而 4,3,5,1,2 非法

以压入序列 1,2,3,4,5 为例,走一遍上面的算法。

弹出序列 4,5,3,2,1(合法):

操作	栈(栈顶在右)	popIndex 期望值
依次压入 1、2、3、4	1,2,3,4	4
栈顶 4 匹配,弹出	1,2,3	5
压入 5	1,2,3,5	5
栈顶 5 匹配,弹出	1,2,3	3
栈顶 3 匹配,弹出	1,2	2
栈顶 2 匹配,弹出	1	1
栈顶 1 匹配,弹出	空	序列结束

循环结束时栈为空,返回 true。

弹出序列 4,3,5,1,2(非法):

操作	栈(栈顶在右)	popIndex 期望值
依次压入 1、2、3、4	1,2,3,4	4
栈顶 4 匹配,弹出	1,2,3	3
栈顶 3 匹配,弹出	1,2	5
压入 5	1,2,5	5
栈顶 5 匹配,弹出	1,2	1

此时外层循环已把所有元素压完,但栈中残留 1,2(栈顶是 2),而期望弹出的是 1——2 压在 1 上面,必须先弹出 2 才能弹出 1,与 popSequence 要求的顺序矛盾。循环结束时栈非空,返回 false,与文档结论一致。

复杂度分析

• 时间复杂度 O(n):n 为序列长度。每个元素最多入栈一次、出栈一次,所有 push/pop 操作总次数不超过 2n,每次为 O(1);
• 空间复杂度 O(n):最坏情况下所有元素依次入栈后无法弹出(如弹出序列恰好逆序压满),模拟栈最多容纳 n 个元素。

边界条件与健壮性补充

文档实现默认两个序列非空且等长(方法开头直接取 pushSequence.length 作为 n)。如果实际调用中可能出现长度不一致或空序列,可以先加防御性判断:

if (pushSequence == null || popSequence == null
        || pushSequence.length != popSequence.length) {
    return false;
}

其他典型边界场景:

• 两序列相同(如 1,2,3 压 1,2,3 弹):每压一个就立刻弹出一个,栈始终不深,返回 true;
• 两序列逆序(如 1,2,3 压 3,2,1 弹):全部压入后从栈顶依次弹出,返回 true;
• 长度不等:弹出序列不可能与压入序列一一对应,直接判 false。

与仓库内其他内容的关联

• 本题在剑指 Offer 题解索引 剑指 Offer 题解 - 目录 中对应条目为 31. 栈的压入、弹出序列,同系列的栈相关题目还有 包含 min 函数的栈 与 用两个栈实现队列,可以对照阅读;
• 模拟过程依赖的 Stack 接口,与仓库 算法 - 栈和队列 中给出的 MyStack 接口定义(push / pop / isEmpty / size)在语义上完全一致,该文件还提供了数组实现 ArrayStack 与链表实现两种自研栈。从源码结构看,本题中的 new Stack<>() 完全可以用该文件里的 ArrayStack 替换——判定逻辑只用到压入、弹栈、看栈顶和判空四种操作,任何标准栈实现都可支撑这道题,这也反过来验证了"判定算法与具体栈的存储结构无关"。

小结

剑指 Offer 31 的本质是用贪心模拟替代组合枚举:不列举所有可能的出入栈操作序列,而是利用"栈顶匹配就立即弹出"的唯一强制性,单趟扫描完成合法性判定。掌握"每压一个元素后尽可能弹出"的循环骨架(外层按序压入、内层 while 匹配弹出、最后判栈空),是解决这类栈序列判定问题的通用模式。