推荐订阅源

验证栈序列，给定push和pop序列，是否可能是一对出栈入栈组合。

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

思路：
利用Stack数据结构。
从j出发：访问到pop[j]的时候，需要把push里对应的这个值的前面所有值都压入栈。
i和j指向当前的push和pop，当栈顶不为pop[j]时，i的值一直入栈并向后移动。然后弹出j的值。最后i遍历完后，验证栈弹出的顺序和j的顺序。
校验条件：

1. 弹出时，一定是j的值。i一直向后移动，可能移动到最后了，还没有j想要的值，这时候栈顶不是j的值，返回false。
2. 最后全体出战与j的顺序

public boolean validateStackSequences(int[] pushed, int[] popped) {
    int n=pushed.length;
    Stack<Integer> stack=new Stack<>();
    int i=0;
    int j=0;
    while(i!=n&&j!=n){
        while(stack.isEmpty()||stack.peek()!=popped[j]){
            stack.push(pushed[i++]);
            if(i==n){
                break;
            }
        }
        //弹出
        if(stack.pop()!=popped[j]){//出栈必须是j的值
            return false;
        }
        j++;   
    }
    while(!stack.isEmpty()&&j!=n){//最后的验证
        int tmp=stack.pop();
        if(tmp!=popped[j++]){
            return false;
        }
    }
    return stack.isEmpty()&&i==n&&j==n;
}

换个方向思考：
从i的角度出发：每次把i的值压入站。连续检查栈顶是不是需要弹出。

public boolean validateStackSequences(int[] pushed, int[] popped) {
    int n=pushed.length;
    int j=0;
    Stack<Integer> stack=new Stack<>();
    for(int val:pushed){
        stack.push(val);
        while(!stack.isEmpty()&&j!=n&&stack.peek()==popped[j]){
            stack.pop();
            j++;
        }
    }
    return j==n;//j!=n等价于stack不为空，因为stack历史总记录是n个
}