题解 | #栈的压入、弹出序列#

判断一个弹出序列会不会是压入序列的弹出序列, 首先要明确, 栈是可以再任意一个时刻弹出任意个元素的, 所以一个压入序列可以有非常多个弹出序列的, 数量可以说是n的阶乘个数量级, 所以不能使用暴力搜索匹配. 我们可以根据题目提供的弹出序列来控制栈的弹出在栈顶元素为弹出序列当前元素时弹出, 按照题目的意愿控制, 最后看栈是否为空, 如果正常, 最后栈应该是空的, 不空的话说明就不是弹出序列中的一个

具体来说, 遍历压入序列,同时创建一个指针k指向弹出序列用来判断, 在每次将元素压入栈中时判断是否与当前弹出序列元素相等, 如果相等的话就要进行弹出操作, 同时k要指向下一个元素, 如此循环直到栈为空/弹出序列已经遍历完/弹出序列当前元素不等于栈顶元素, 此时就进入压入序列下一个元素的判断

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型一维数组 
     * @param popV int整型一维数组 
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        //肯定是不可能暴力搜索匹配的 阶乘复杂度太高
        //那么可以按照指定的出栈顺序对栈进行操作, 看最后栈是否为空
        //主要是要确定这个数是不是一入栈就出栈了
        //每压入一个数, 就看是否和当前顺序数匹配, 如果匹配就出栈
        Stack<Integer> stack = new Stack<>();
        int k = 0;
        for(int i=0;i<pushV.length;i++) {
            stack.push(pushV[i]);
            while(!stack.empty() && stack.peek() == popV[k] && k<popV.length) {
                stack.pop();
                k++;
            }
        }
        return stack.empty();
    }
}