0946. 验证栈序列

0946. 验证栈序列 #

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

题目大意 #

描述:给定两个整数序列 pushedpopped,每个序列中的值都不重复。

要求:如果第一个序列为空栈的压入顺序,而第二个序列 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)$。
本站总访问量  次  |  您是本站第  位访问者