栈的压入、弹出序列

题目的主要信息：

• 给定两个序列，第一个表示入栈顺序，第二个表示出栈顺序
• 序列中没有重复的数字
• 判定第一个入栈顺序能否得到第二个出栈顺序

举一反三：

学习完本题的思路你可以解决如下题目：

JZ9. 用两个栈实现队列

JZ30. 包含min函数的栈

方法一：辅助栈（推荐使用）

知识点：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：

题目要我们判断两个序列是否符合入栈出栈的次序，我们就可以用一个栈来模拟。对于入栈序列，只要栈为空，序列肯定要依次入栈。那什么时候出来呢？自然是遇到一个元素等于当前的出栈序列的元素，那我们就放弃入栈，让它先出来。

//入栈：栈为空或者栈顶不等于出栈数组
while(j < n && (s.isEmpty() || s.peek() != popA[i])){
    s.push(pushA[j]);
    j++;
}

如果能按照这个次序将两个序列都访问完，那说明是可以匹配入栈出栈次序的。

具体做法：

• step 1：准备一个辅助栈，两个下标分别访问两个序列。
• step 2：辅助栈为空或者栈顶不等于出栈数组当前元素，就持续将入栈数组加入栈中。
• step 3：栈顶等于出栈数组当前元素就出栈。
• step 4：当入栈数组访问完，出栈数组无法依次弹出，就是不匹配的，否则两个序列都访问完就是匹配的。

图示：

Java实现代码：

import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int n = pushA.length;
        //辅助栈
        Stack<Integer> s = new Stack<>();
        //遍历入栈的下标
        int j = 0;
        //遍历出栈的数组
        for(int i = 0; i < n; i++){
            //入栈：栈为空或者栈顶不等于出栈数组
            while(j < n && (s.isEmpty() || s.peek() != popA[i])){
                s.push(pushA[j]);
                j++;
            }
            //栈顶等于出栈数组
            if(s.peek() == popA[i])
                s.pop();
            //不匹配序列
            else
                return false;
        }
        return true;
    }
}

C++实现代码：

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int n = pushV.size();
        //辅助栈
        stack<int> s;
        //遍历入栈的下标
        int j = 0;
        //遍历出栈的数组
        for(int i = 0; i < n; i++){
            //入栈：栈为空或者栈顶不等于出栈数组
            while(j < n && (s.empty() || s.top() != popV[i])){
                s.push(pushV[j]);
                j++;
            }
            //栈顶等于出栈数组
            if(s.top() == popV[i])
                s.pop();
            //不匹配序列
            else
                return false;
        }
        return true;
    }
};

Python实现代码：

class Solution:
    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        n = len(pushV)
        #辅助栈
        s = []
        #遍历入栈的下标
        j = 0
        #遍历出栈的数组
        for i in range(n):
            #入栈：栈为空或者栈顶不等于出栈数组
            while j < n and (len(s) == 0 or s[-1] != popV[i]):
                s.append(pushV[j])
                j += 1
            #栈顶等于出栈数组
            if s[-1] == popV[i]:
                s.pop()
            #不匹配序列
            else:
                return False
        return True

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为数组长度，最坏情况下需要遍历两个数组各一次
• 空间复杂度：$O(n)O(n)$，辅助栈空间最大为一个数组的长度

方法二：原地栈（扩展思路）

思路：

方法一我们使用了一个辅助栈来模拟，但是数组本来就很类似栈啊，用下标表示栈顶。在方法一种push数组前半部分入栈了，就没用了，这部分空间我们就可以用来当成栈。原理还是同方法一一样，只是这时我们遍历push数组的时候，用下标n表示栈空间，n的位置就是栈顶元素。

具体做法：

• step 1：用下标n表示栈空间，用j表示出栈序列的下标。
• step 2：遍历每一个待入栈的元素，加入栈顶，即push数组中n的位置，同时增加栈空间的大小，即n的大小。
• step 3：当栈不为空即栈顶n大于等于0，且栈顶等于当前出栈序列，就出栈，同时缩小栈的空间，即减小n。
• step 4：最后若是栈空间大小n为0，代表全部出栈完成，否则不匹配。

图示：

Java实现代码：

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        //表示栈空间的大小，初始化为0
        int n = 0;
        //出栈序列的下标
        int j = 0;
        //对于每个待入栈的元素
        for(int num : pushA){
            //加入栈顶
            pushA[n] = num;
            //当栈不为空且栈顶等于当前出栈序列
            while(n >= 0 && pushA[n] == popA[j]){
                //出栈，缩小栈空间
                j++;
                n--;
            }
            n++;
        }
        //最后的栈是否为空
        return n == 0;
    }
}

C++实现代码：

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        //表示栈空间的大小，初始化为0
        int n = 0;
        //出栈序列的下标
        int j = 0;
        //对于每个待入栈的元素
        for(int num : pushV){
            //加入栈顶
            pushV[n] = num;
            //当栈不为空且栈顶等于当前出栈序列
            while(n >= 0 && pushV[n] == popV[j]){
                //出栈，缩小栈空间
                j++;
                n--;
            }
            n++;
        }
        //最后的栈是否为空
        return n == 0;
    }
};

Python实现代码：

class Solution:
    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        #表示栈空间的大小，初始化为0
        n = 0
        #出栈序列的下标
        j = 0
        #对于每个待入栈的元素
        for num in pushV:
            #加入栈顶
            pushV[n] = num
            #当栈不为空且栈顶等于当前出栈序列
            while n >= 0 and pushV[n] == popV[j]:
                #出栈，缩小栈空间
                j += 1
                n -= 1
            n += 1
        #最后的栈是否为空
        return True if n == 0 else False

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为数组长度，最坏还是遍历两个数组
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间