剑指 Offer 31. 栈的压入、弹出序列

解题思路：模拟

如示例：

  1. pushed = {2,3,0,1}
  2. popped = {0,3,2,1}

该结果返回 true，我们可以按照以下的顺序入栈出栈：

  1. push(2)
  2. push(3)
  3. push(0)
  4. pop(0)
  5. pop(3)
  6. pop(2)
  7. push(1)
  8. pop(1)

本题的解题思路为模拟，顾名思义，我们将使用一个辅助栈来模拟整个栈的压入与弹出过程

算法流程：

  • 初始化辅助栈 stack

  • 首先判断 pushed 数组长度是否与 popped 数组长度相等，如果不等，直接返回 false

  • 遍历压栈序列

    • 压栈序列中的各元素记作 num，首先 num 入栈

    • 循环出栈：如果 stack 栈顶的元素 = 弹出序列元素 popped[i]，则执行出栈操作以及 i++

  • 最后判断 stack 是否为空，作为返回值

代码

  1. class Solution {
  2.     public boolean validateStackSequences(int[] pushed, int[] popped) {
  3.         if(pushed.length != popped.length){
  4.             return false;
  5.         }
  6.         Stack<Integer> stack = new Stack<>();
  7.         int i = 0;
  8.         for(int num : pushed){
  9.             stack.push(num);
  10.             while(!stack.isEmpty() && stack.peek() == popped[i]){
  11.                 stack.pop();
  12.                 i++;
  13.             }
  14.         }
  15.         return stack.isEmpty();
  16.     }
  17. }

复杂度分析

  • 时间复杂度：O(N)

我们将 pushed 序列从头至尾遍历，模拟了压栈出栈的过程，时间复杂度为：O(N)

  • 空间复杂度：O(N)

我们额外使用了 stack 作为辅助栈来进行模拟，所以额外空间复杂度为：O(N)