当前位置：首页 > news >正文

Leetcode 946.验证栈序列

news 来源：原创 2024/5/5 18:09:23

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

复杂度分析

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

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