题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
示例1: 输入：[1,2,3,4,5],[4,3,5,1,2]
返回值：false

题目分析

因为栈的数据操作具有“先入后出”的特点，数据只能按照从上到下的顺序弹出，位于下面的数据不能先于上面的数据弹出。
图片说明
比如示例1，入栈顺序为（1,2,3,4,5），可能的出栈顺序有：
1.（5,4,3,2,1），这种情况是直到数据全部入栈后再出栈；其他情况可以只一部分数据入栈后立即出栈；
2.（4,5,3,2,1），这种情况是先入（1,2,3,4），出栈（4），再入（5），出栈（5,3,2,1）；
3.对于情况（4,3,5,1,2），可以先入（1,2,3,4），出栈（4,3），再入（5），出栈（5），在这里栈中的数据2在1的上面，所以只能先出2，再出1，而不能（1,2），所以这种情况不符合要求。

解题思路

1.因为弹出序列是要依据压入序列来判断的，所以首先要遍历压入序列数组；
2.在遍历压入数组时，每次都需要判断当前数值是否是弹出，即比较pushA[i] == popA[j]，相同即弹出，不同则将数据压入栈；
3.不断比较，遍历完成后，判断数据是否全部出栈。

代码实现

方法一：使用栈来模拟压入和弹出的顺序，最后判断栈是否为空

public boolean IsPopOrder(int [] pushA,int [] popA) {
      // 使用辅助栈
      Stack<integer> stack = new Stack<>();
      // 出栈数组下标
      int j = 0;
      for (int i=0;i<pushA.length;i++) {
            stack.push(pushA[i]);
            // 若stack的顶部数据与popa出栈数字相同，则数据出栈
            while (!stack.isempty() && stack.peek()="=" popA[j]) {
               stack.pop();
               j++;
            }
      }
      return stack.isEmpty();
}

时间复杂度为o(n)，其中 n 为数组 pushA 的长度；每个元素最多入栈与出栈一次（只有相同的才会执行循环），即最多共 2n 次出入栈操作。
空间复杂度为o(n)，辅助栈 stackstack 最多同时存储 n 个元素。

方法二：使用变量size来代替栈，可以降低空间复杂度

public boolean ispoporder(int [] pushA,int popA) {
     // size表示目前存入栈的数字数量,j 出栈数组下标
     int size = 0, j = 0;
     for (int e : pushA) {
        // 每次更新栈顶数据
          pushA[size] = e;
        // 若stack的顶部数据与popa出栈数字相同，则数据出栈
          while (size >= 0 && pushA[size] == popA[j]) {
                j++;
                size--;
          }
          size++;
     }
     return size == 0;
}

时间复杂度为O(n)，其中 n 为数组 pushA 的长度；每个元素最多入栈与出栈一次（只有相同的才会执行循环），即最多共 2n 次出入栈操作。
空间复杂度为O(1)，因为没有使用辅助栈，只使用size变量来抽象表示栈的容量。