31 栈的压入、弹出序列

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

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

解题思路：

根据已有的压入序列，我们借助一个辅助栈 $S$，模拟压入。

压入过程中，使用索引 $k$ 来指向弹出序列，如果 k 指向的弹出元素和当前 $S$ 的栈顶元素相同，则将 $S$ 的栈顶元素弹出，$k$ 自增，否则继续将压入序列压入 $S$ 中。

如果压入序列遍历完了，$S$ 中还有数据，说明弹出序列不合法，否则 $S$ 应该为空。

验证函数

传递参数： 压入序列 $pushed$，弹出序列 $popped$。

验证过程：

• 创建一个模拟栈 $S$，弹出元素的索引 $k$ 初始值为 $0$。
• 遍历 $pushed$，用 $num$ 表示当前压入元素
  • 将 $num$ 压入 $S$ 中。
  • 循环检查，当 $S$ 不为空时，检查 $S$ 的栈顶元素是否等于 $popped[k]$
    • 如果相等，则 $S$ 弹出栈顶元素，$k$ 自增
• 判断 $S$ 是否为空
  • $false$：$S$ 不为空，$popped$ 不合法；
  • $true$：$S$ 为空，$popped$ 合法

代码：

public boolean validateStackSequences(int[] pushed, int[] popped) {
    if (pushed == null || popped == null
            || pushed.length == 0 || pushed.length != popped.length) {
        return true;
    }
    // helper 来模拟 pushed 的入栈
    Deque<Integer> helper = new LinkedList<>();
    int k = 0;
    for (int num : pushed) {
        // 模拟入栈
        helper.push(num);
        // 如果辅助栈不为空，检查辅助栈的栈顶元素，如果和弹出序列相等就弹出
        while (!helper.isEmpty() && helper.peek() == popped[k]) {
            helper.pop();
            k++;
        }
    }
    return helper.isEmpty();
}

复杂度分析

• 时间复杂度$O(N)$：$N$ 为 $pushed$ 的长度，每个元素最多出入栈 $2$ 次，即最多共 $2N$ 次出入栈操作。
• 空间复杂度$O(N)$：$N$ 为 $pushed$ 的长度，辅助栈最多存储 $N$ 个元素。