难度：★★★☆☆
类型：栈
方法：栈

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定 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 的排列。

解答

准备一个栈stack，逐个的将pushed序列中的元素入栈，每次入栈一个元素，都要及时判断，当前的栈顶元素stack[-1]是否与当前poped序列中的队首元素poped[0]一致，如果一致，则将栈顶元素弹出，并及时更新poped序列，即队首出列，使用while循环进行连续的控制，直到不再满足stack[-1]==poped[0]为止。

最后，如果poped队列中还有没有使用的元素，则说明过程失败，否则成功。

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        stack = []
        for x in pushed:
            stack.append(x)
            while stack and stack[-1] == popped[0]:
                stack.pop()
                popped.pop(0)
        return not popped

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析