0946. 验证栈序列 #

标签：栈、数组、模拟
难度：中等

题目大意 #

描述：给定两个整数序列 pushed 和 popped，每个序列中的值都不重复。

要求：如果第一个序列为空栈的压入顺序，而第二个序列 popped 为该栈的压出序列，则返回 True，否则返回 False。

说明：

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

示例：

示例 1：

1
2
3
4
5


输入：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：

1
2
3


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

解题思路 #

思路 1：栈 #

借助一个栈来模拟压入、压出的操作。检测最后是否能模拟成功。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        index = 0
        for item in pushed:
            stack.append(item)
            while (stack and stack[-1] == popped[index]):
                stack.pop()
                index += 1

        return len(stack) == 0

思路 1：复杂度分析 #

时间复杂度：$O(n)$。
空间复杂度：$O(n)$。