快乐的LeetCode --- 面试题31. 栈的压入、弹出序列

一时失言乱红尘 2023-02-18 09:48 2阅读 0赞

**题目描述：**

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 `{1,2,3,4,5}` 是某栈的压栈序列，序列 `{4,5,3,2,1}` 是该压栈序列对应的一个弹出序列，但 `{4,3,5,1,2}` 就不可能是该压栈序列的弹出序列。

**示例 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 之前弹出。

--------------------

**解题思路:**

每次入栈后，循环判断 “栈顶元素 == 弹出序列的当前元素” 是否成立，将符合弹出序列顺序的栈顶元素全部弹出。

--------------------

**代码：**

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

--------------------

**题目来源：**

[https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof][https_leetcode-cn.com_problems_zhan-de-ya-ru-dan-chu-xu-lie-lcof]

[https_leetcode-cn.com_problems_zhan-de-ya-ru-dan-chu-xu-lie-lcof]: https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof