image.png

解:

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed.length==0||popped.length==0)return true;
        Deque<Integer> stack = new LinkedList<>();
        int j =0;
        for(int num:pushed){
            stack.push(num);
            while(!stack.isEmpty()&&stack.peek()==popped[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

从压入序列开始。

Q.E.D.