31 栈的压入、弹出序列

Lin2J
2021-07-21 / 0 评论 / 72 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 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$ 个元素。