剑指offer-21、栈的压⼊、弹出序列

题⽬描述

输⼊两个整数序列，第⼀个序列表示栈的压⼊顺序，请判断第⼆个序列是否可能为该栈的弹出顺序。假设压⼊栈的所有数字均不相等。例如序列1,2,3,4,5 是某栈的压⼊顺序，序列4,5,3,2,1 是该压栈序列对应的⼀个弹出序列，但4,3,5,1,2 就不可能是该压栈序列的弹出序列。（注意：这两个序列的⻓度是相等的）

示例1
输⼊：[1,2,3,4,5],[4,5,3,2,1]
返回值：true
说明：可以通过push(1) => push(2) => push(3) => push(4) => pop() => push(5)=> pop() => pop() => pop() => pop()；这样的顺序得到 [4,5,3,2,1] 这个序列，返回 true

思路及解答

辅助栈模拟（推荐）

使用一个辅助栈来模拟压入和弹出过程：

1. 初始化一个空栈和指向弹出序列的指针
2. 遍历压入序列，依次将元素压入栈中
3. 每次压入后，检查栈顶元素是否等于当前弹出序列元素
   • 如果相等，则弹出栈顶元素并移动弹出序列指针
   • 重复此过程直到不相等为止
4. 最后检查栈是否为空，为空则表示弹出序列可行

public class Solution {
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        // 边界条件检查
        if (pushA == null || popA == null || pushA.length == 0 || popA.length == 0 || pushA.length != popA.length) {
            return false;
        }
        
        Stack<Integer> stack = new Stack<>(); // 辅助栈
        int popIndex = 0; // 弹出序列指针
        
        for (int pushValue : pushA) {
            stack.push(pushValue); // 压入当前元素
            // 循环检查栈顶是否等于当前弹出元素
            while (!stack.isEmpty() && stack.peek() == popA[popIndex]) {
                stack.pop(); // 弹出匹配元素
                popIndex++; // 移动弹出序列指针
            }
        }
        
        return stack.isEmpty(); // 栈空表示全部匹配
    }
}

• 时间复杂度： O(n)
• 空间复杂度： O(n) , 借助了额外的栈空间，最坏情况下会全部⼊栈。

双指针法

利用原数组作为栈空间，通过双指针模拟栈操作：

1. 使用压入序列本身作为栈空间
2. 通过栈指针和弹出序列指针同步移动
3. 直接在原数组上进行"压入"和"弹出"操作

public class Solution {
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        if (pushA == null || popA == null || pushA.length != popA.length) {
            return false;
        }
        
        int stackTop = -1; // 栈指针
        int popIndex = 0; // 弹出序列指针
        
        for (int pushValue : pushA) {
            pushA[++stackTop] = pushValue; // 利用原数组存储
            // 检查并"弹出"
            while (stackTop >= 0 && pushA[stackTop] == popA[popIndex]) {
                stackTop--;
                popIndex++;
            }
        }
        
        return stackTop == -1;
    }
}

• 时间复杂度​：O(n)
• ​空间复杂度​：O(1)，仅使用固定数量的指针变量

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top