剑指offer-21、栈的压⼊、弹出序列
题⽬描述输⼊两个整数序列，第⼀个序列表示栈的压⼊顺序，请判断第⼆个序列是否可能为该栈的弹出顺序。假设压⼊栈的所有数字均不相等。例如序列1,2,3,4,5 是某栈的压⼊顺序，序列4,5,3,2,1 是该压栈序列对应的⼀个弹出序列，但4,3,5,1,2 就不可能是该压栈序列的弹出序列。（注意：这两个序列的⻓度是相等的）
示例1
输⼊：,
返回值：true
说明：可以通过push(1) => push(2) => push(3) => push(4) => pop() => push(5)=> pop() => pop() => pop() => pop()；这样的顺序得到 这个序列，返回 true
思路及解答
辅助栈模拟（推荐）
使用一个辅助栈来模拟压入和弹出过程：
[*]初始化一个空栈和指向弹出序列的指针
[*]遍历压入序列，依次将元素压入栈中
[*]每次压入后，检查栈顶元素是否等于当前弹出序列元素
[*]如果相等，则弹出栈顶元素并移动弹出序列指针
[*]重复此过程直到不相等为止
[*]最后检查栈是否为空，为空则表示弹出序列可行
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) {
stack.pop(); // 弹出匹配元素
popIndex++; // 移动弹出序列指针
}
}
return stack.isEmpty(); // 栈空表示全部匹配
}
}
[*]时间复杂度： O(n)
[*]空间复杂度： O(n) , 借助了额外的栈空间，最坏情况下会全部⼊栈。
双指针法
利用原数组作为栈空间，通过双指针模拟栈操作：
[*]使用压入序列本身作为栈空间
[*]通过栈指针和弹出序列指针同步移动
[*]直接在原数组上进行"压入"和"弹出"操作
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 == popA) {
stackTop--;
popIndex++;
}
}
return stackTop == -1;
}
}
[*]时间复杂度：O(n)
[*]空间复杂度：O(1)，仅使用固定数量的指针变量
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]