剑指Offer.31 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof

解题思路

扫描数组pushed, 并用一个索引指向popped, 将pushed当前遍历的元素压入栈
当刚入栈的pushed元素不是popped索引所指元素时, 继续往后扫描pushed
反之弹出栈顶元素, 并将popped的索引右移
如果遍历完整个数组, 栈中还有剩余元素, 则返回false, 栈为空则返回true

代码

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed == null || popped == null) {
            return false;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        int popIndex = 0;
        // 当pushed栈顶不是popped的栈顶时, 将pushed压入辅助栈
        for (int num : pushed) {
            stack.push(num);
            while (!stack.isEmpty() && stack.element() == popped[popIndex]) {
                stack.pop();
                popIndex++;
            }
        }
        return stack.isEmpty();
    }
}