验证栈序列 [中等]
给定 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 之前弹出.
提示:
- 0 <= pushed.length == popped.length <= 1000
- 0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列.
解题思路
按照题目的要求, 就是要将 pushed 里的元素按顺序压入栈, 并且可以按照 popped 的顺序弹出. 那我们就必须要将 pushed 里的元素按顺序压入, 直到栈顶是 popped 的第一个元素为止就弹出, 大概就是这个过程, 主要考查的就是对栈的理解. 代码如下:
- class Solution(object):
- def validateStackSequences(self, pushed, popped):
- """
- :type pushed: List[int]
- :type popped: List[int]
- :rtype: bool
- """
- stack = []
- i = 0
- for j in pushed:
- stack.append(j)
- while stack and stack[-1] == popped[i]:
- stack.pop()
- i = i + 1
- return not stack
来源: http://www.jianshu.com/p/36742115911d