剑指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. public class Solution {
2.     public boolean IsPopOrder(int[] pushA, int[] popA) {
3.         // 边界条件检查
4.         if (pushA == null || popA == null || pushA.length == 0 || popA.length == 0 || pushA.length != popA.length) {
5.             return false;
6.         }
7.         
8.         Stack<Integer> stack = new Stack<>(); // 辅助栈
9.         int popIndex = 0; // 弹出序列指针
10.         
11.         for (int pushValue : pushA) {
12.             stack.push(pushValue); // 压入当前元素
13.             // 循环检查栈顶是否等于当前弹出元素
14.             while (!stack.isEmpty() && stack.peek() == popA[popIndex]) {
15.                 stack.pop(); // 弹出匹配元素
16.                 popIndex++; // 移动弹出序列指针
17.             }
18.         }
19.         
20.         return stack.isEmpty(); // 栈空表示全部匹配
21.     }
22. }

复制代码

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

双指针法

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

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

1. public class Solution {
2.     public boolean IsPopOrder(int[] pushA, int[] popA) {
3.         if (pushA == null || popA == null || pushA.length != popA.length) {
4.             return false;
5.         }
6.         
7.         int stackTop = -1; // 栈指针
8.         int popIndex = 0; // 弹出序列指针
9.         
10.         for (int pushValue : pushA) {
11.             pushA[++stackTop] = pushValue; // 利用原数组存储
12.             // 检查并"弹出"
13.             while (stackTop >= 0 && pushA[stackTop] == popA[popIndex]) {
14.                 stackTop--;
15.                 popIndex++;
16.             }
17.         }
18.         
19.         return stackTop == -1;
20.     }
21. }

复制代码

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。