Leetcode 946.验证栈序列

1.题目描述

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

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

输入：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 的一个排列

2.思路分析

2.1 栈模拟

对于题目给定的pushed和poped数组的如下性质:

• 数组 pushed 中的元素互不相同；
• 数组 popped 和数组 pushed 的长度相同；
• 数组 popped 是数组 pushed 的一个排列。

根据上述性质,可以得出:

• 栈内不会出现重复元素

• 如果pushed 和 popped 是有效的栈操作序列，则经过所有的入栈和出栈操作之后，每个元素各

  入栈和出栈一次，栈为空。

遍历两个数组，模拟入栈和出栈操作，判断两个数组是否为有效的栈操作序列。

模拟入栈可以通过遍历pushed数组实现，由于只有栈顶的元素可以出栈，因此模拟出栈操作需要判

断栈顶元素是否与popped数组中当前元素相同(相同栈顶元素出栈)。

具体步骤:

• 遍历数组 pushed，将 pushed 的每个元素依次入栈；

• 每pushed 的元素入栈之后，如果栈不为空且栈顶元素与 popped 的当前元素相同，则将栈顶元

  素出栈，同时遍历数组 popped，直到栈为空或栈顶元素与 popped 的当前元素不同。

• 遍历数组 pushed 结束之后，每个元素都按照数组 pushed 的顺序入栈一次。

• 如果栈为空, 每个元素都按照数组popped的顺序出栈, 返回true

• 如果栈不为空,每个元素都不能按照数组popped的顺序出栈, 返回false

举个栗子:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

• 模拟入栈操作
  

• 模拟出栈

• 遍历结束后

3.代码实现

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        # 定义栈(初始化为空)以及指针(指向popped数组,初始化为0)
        stack, pi = [], 0
        # 遍历pushed数组
        for i in range(len(pushed)):
            # 模拟入栈 pushed数组元素入栈
            stack.append(pushed[i])
            # 模拟出栈,当栈存在且栈顶元素等于popped当前元素,出栈
            while stack and stack[-1] == popped[pi]:
                stack.pop()
                pi += 1
        # 遍历结束后, 栈为空返回true 反之false
        return not stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 pushed 和 popped 的长度。需要遍历数组 pushed 和 popped 各一次，判断两个数组是否为有效的栈操作序列。

• 空间复杂度：O(n)，其中 nn 是数组 pushed 和popped 的长度。空间复杂度主要取决于栈空间，栈内元素个数不超过 n。