What is the main strategy for Validate Stack Sequences?

Simulate a stack pushing elements from pushed and popping when the top matches the next popped element.

Can I use recursion instead of an explicit stack?

Yes, recursion can mimic the stack behavior but may increase call stack usage; the iterative stack is simpler and safer.

What if pushed and popped arrays have different lengths?

The sequence is invalid; they must have the same length and contain the same unique elements.

How do I handle an empty pushed array?

An empty pushed array is valid only if the popped array is also empty, otherwise return false.

Why does the stack top check fail in some sequences?

The stack top check fails when a pop operation is attempted before the corresponding element is pushed, violating stack order.

#946

Medium

auto_awesome栈·状态

LeetCode 题解工作台

验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true ；否则，返回 false 。示例 1：输入： pushed = [1,2,3,4,5], popped = [4,5,3…

数组栈模拟

题目描述

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：

1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed 的所有元素 互不相同
popped.length == pushed.length
popped 是 pushed 的一个排列

lightbulb

解题思路

方法一：栈模拟

我们遍历 $\textit{pushed}$ 数组，对于当前遍历到的元素 $x$ ，我们将其压入栈 $\textit{stk}$ 中，然后判断栈顶元素是否和 $\textit{popped}$ 数组中下一个要弹出的元素相等，如果相等，我们就将栈顶元素弹出并将 $\textit{popped}$ 数组中下一个要弹出的元素的索引 $i$ 加一。最后，如果要弹出的元素都能按照 $\textit{popped}$ 数组的顺序弹出，返回 $\textit{true}$ ，否则返回 $\textit{false}$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为 $\textit{pushed}$ 数组的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stk = []
        i = 0
        for x in pushed:
            stk.append(x)
            while stk and stk[-1] == popped[i]:
                stk.pop()
                i += 1
        return i == len(popped)

speed

复杂度分析

指标	值
时间	complexity is O(n) since each element is pushed and popped at most once. Space complexity is O(n) to store the stack in the worst case, proportional to the length of the pushed array.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looking for clear stack simulation and pointer usage.
question_mark
Expect recognition that element order in pushed matters.
question_mark
Watch for correct handling of stack top matching popped elements.

warning

常见陷阱

外企场景

error
Attempting to pop elements in an order not allowed by the stack.
error
Forgetting to check stack top against the current popped element repeatedly.
error
Assuming sequences are valid without simulating push and pop accurately.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Sequences where pushed and popped include duplicate values.
arrow_right_alt
Larger arrays requiring optimized in-place simulation.
arrow_right_alt
Generating the valid popped sequence given a random pushed array.

help

常见问题

外企场景

继续练习

#735 小行星碰撞 #682 棒球比赛 #1441 用栈操作构建数组