946. 验证栈序列

946. 验证栈序列

题目描述

给定两个整数数组 pushed 和 popped，其中：

  • pushed 表示压入栈的顺序
  • popped 表示弹出栈的顺序

请你判断 popped 是否有可能是 pushed 的一个合法弹出序列。

如果是，返回 true；否则返回 false。

示例 1

text
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true

示例 2

text
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false

约束

  • 1 <= pushed.length <= 1000
  • 0 <= pushed[i] <= 1000
  • pushed.length == popped.length
  • pushed 是 0 到 pushed.length - 1 的一个排列
  • popped 是 pushed 的一个排列

核心思路

这题本质上不是“猜序列”，而是：

  • 按 pushed 的顺序模拟入栈
  • 只要栈顶等于 popped 当前想弹出的值，就立刻弹出

也就是说，我们只需要老老实实模拟真实栈过程。

这题至少有两种常见做法：

  • 解法一：辅助栈模拟（推荐）
  • 解法二：原地把 pushed 当栈用

解法一：辅助栈模拟

这是最标准、最推荐掌握的做法。

思路拆解

遍历 pushed：

  1. 每来一个数，先入栈
  2. 然后检查：当前栈顶是不是正好等于 popped[j]
  3. 如果相等，就不断弹栈，并让 j++
  4. 最后如果栈能完全按 popped 匹配完，就是合法序列

一步一步写出算法

第一步：定义辅助栈和弹出指针

ts
const stack: number[] = []
let j = 0

第二步：按顺序压栈

ts
for (const num of pushed) {
    stack.push(num)
}

但每次压栈后，都要立刻尝试弹出。

第三步：只要栈顶能匹配，就连续弹出

ts
while (stack.length > 0 && stack[stack.length - 1] === popped[j]) {
    stack.pop()
    j++
}

第四步：最后判断是否全部匹配完

ts
return j === popped.length

代码实现（TypeScript）

ts
function validateStackSequences(pushed: number[], popped: number[]): boolean {
    const stack: number[] = []
    let j = 0

    for (const num of pushed) {
        stack.push(num)

        while (stack.length > 0 && stack[stack.length - 1] === popped[j]) {
            stack.pop()
            j++
        }
    }

    return j === popped.length
}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

因为每个元素最多入栈、出栈各一次。

这一解法的优缺点

优点：

  • 最直观
  • 最容易写对
  • 是标准解法

缺点：

  • 需要额外一个辅助栈

解法二：原地把 pushed 当栈用

这个做法本质一样，只是节省了额外栈空间。

思路拆解

我们把 pushed 数组本身当成栈空间：

  • 用 top 表示当前栈顶位置
  • 每读入一个 pushed[i]，就把它写到 pushed[top]
  • 然后照样尝试和 popped[j] 匹配弹出

这样就不需要额外申请一个新数组作为栈。

一步一步写出算法

第一步：定义两个指针

ts
let top = 0
let j = 0

这里 top 表示当前栈里元素个数。

第二步：把当前元素压进“模拟栈”

ts
pushed[top] = num
top++

第三步：只要栈顶匹配就弹出

ts
while (top > 0 && pushed[top - 1] === popped[j]) {
    top--
    j++
}

第四步：判断是否全部匹配完成

ts
return j === popped.length

代码实现（TypeScript）

ts
function validateStackSequences(pushed: number[], popped: number[]): boolean {
    let top = 0
    let j = 0

    for (const num of pushed) {
        pushed[top] = num
        top++

        while (top > 0 && pushed[top - 1] === popped[j]) {
            top--
            j++
        }
    }

    return j === popped.length
}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(1) 额外空间

这一解法的优缺点

优点：

  • 额外空间更省
  • 本质和标准栈模拟一样

缺点：

  • 会修改输入数组
  • 可读性不如辅助栈版本

两种解法对比

解法时间复杂度空间复杂度特点
辅助栈模拟O(n)O(n)最标准，最推荐
原地模拟栈O(n)O(1)更省空间

如果你是第一次做这题，建议优先掌握第一种。

手动模拟一遍

以：

text
pushed = [1,2,3,4,5]
popped = [4,5,3,2,1]

为例。

前四次压栈

依次压入：

text
1, 2, 3, 4

当前栈顶是 4，刚好等于 popped[0]。

所以弹出 4。

再压入 5

当前栈：

text
[1,2,3,5]

栈顶 5 等于 popped[1]，弹出。

然后栈顶 3 等于 popped[2]，继续弹。

接着：

  • 弹 2
  • 弹 1

最后正好全部匹配完。

所以答案是：

text
true

面试时最容易错的点

1. 不是随便猜顺序，而是严格模拟栈

栈只有一个规则：

  • 后进先出

所以必须真的按栈行为一步步模拟。

2. 每次压栈后要“尽可能连续弹栈”

不是只弹一次，而是：

ts
while (...)

3. 最后看的是 popped 有没有匹配完

通常写成：

ts
j === popped.length

一句话总结

这题的本质是：

按 pushed 的顺序模拟入栈，并在可能时尽量按 popped 顺序弹栈。

  • 想写标准解：用 辅助栈模拟
  • 想省空间：用 原地模拟栈

推荐你最后记住的标准写法

ts
function validateStackSequences(pushed: number[], popped: number[]): boolean {
    const stack: number[] = []
    let j = 0

    for (const num of pushed) {
        stack.push(num)

        while (stack.length > 0 && stack[stack.length - 1] === popped[j]) {
            stack.pop()
            j++
        }
    }

    return j === popped.length
}

因为这个版本：

  • 最直观
  • 最稳定
  • 是这题公认的标准解法