题⽬描述
输⼊两个整数序列，第⼀个序列表示栈的压⼊顺序，请判断第⼆个序列是否可能为该栈的弹出顺序。假设压⼊栈的所有数字均不相等。例如序列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
思路及解答
辅助栈模拟（推荐）
使用一个辅助栈来模拟压入和弹出过程：
- 初始化一个空栈和指向弹出序列的指针
- 遍历压入序列，依次将元素压入栈中
- 每次压入后，检查栈顶元素是否等于当前弹出序列元素
- 如果相等，则弹出栈顶元素并移动弹出序列指针
- 重复此过程直到不相等为止
- 最后检查栈是否为空，为空则表示弹出序列可行
具体可看下图：遍历压入序列 pushA，每次将当前元素压入辅助栈。压入后，立刻检查辅助栈栈顶是否等于弹出序列 popA 当前指针指向的元素。如果相等，就弹出栈顶，并将 popIndex 向后移动一位。
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) , 借助了额外的栈空间，最坏情况下会全部⼊栈。
双指针法
这个优化版本不再额外创建 Stack 对象，而是直接复用 pushA 数组本身作为临时栈空间。
stackTop 表示当前栈顶下标，初始值为 -1。遍历压入序列时，每读到一个 pushValue，就执行 pushA[++stackTop] = pushValue，相当于把元素压入数组前缀形成的“栈”中。
每次写入后，检查 pushA[stackTop] 是否等于 popA[popIndex]。如果相等，就说明当前栈顶元素可以按照弹出序列弹出，于是执行 stackTop-- 模拟出栈，同时 popIndex++ 移动到下一个待匹配元素。
这个检查使用 while 循环，因为一次压入后可能触发连续弹出。最后如果 stackTop == -1，说明临时栈中的元素全部匹配弹出，弹出序列合法；否则不合法。
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)，仅使用固定数量的指针变量