21 栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

示例：

输入: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出: True

输入: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出: False

解题思路

核心思想：模拟栈的压入和弹出过程。

关键步骤：

1. 创建一个模拟栈
2. 按压入顺序依次压入元素
3. 每压入一个元素，检查栈顶是否等于弹出序列的下一个元素
4. 如果相等则弹出，继续检查
5. 最后检查模拟栈是否为空

时间复杂度：O(n) 空间复杂度：O(n)

Python 实现

def is_valid_stack_sequence(pushed, popped):
    """
    判断popped是否是pushed的合法弹出序列

    Args:
        pushed: 压入序列
        popped: 弹出序列

    Returns:
        bool: 是否合法
    """
    if len(pushed) != len(popped):
        return False

    stack = []
    pop_index = 0

    for num in pushed:
        stack.append(num)

        # 检查栈顶是否等于下一个要弹出的元素
        while stack and stack[-1] == popped[pop_index]:
            stack.pop()
            pop_index += 1

    return not stack


# 测试代码
if __name__ == "__main__":
    test_cases = [
        ([1, 2, 3, 4, 5], [4, 5, 3, 2, 1]),  # True
        ([1, 2, 3, 4, 5], [4, 3, 5, 1, 2]),  # False
        ([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]),  # True
    ]

    for pushed, popped in test_cases:
        result = is_valid_stack_sequence(pushed, popped)
        print(f"pushed={pushed}, popped={popped} → {result}")

# 输出:
# pushed=[1, 2, 3, 4, 5], popped=[4, 5, 3, 2, 1] → True
# pushed=[1, 2, 3, 4, 5], popped=[4, 3, 5, 1, 2] → False
# pushed=[1, 2, 3, 4, 5], popped=[1, 2, 3, 4, 5] → True

图解

示例: pushed=[1,2,3,4,5], popped=[4,5,3,2,1]

压入1, 栈=[1], 栈顶1≠4
压入2, 栈=[1,2], 栈顶2≠4
压入3, 栈=[1,2,3], 栈顶3≠4
压入4, 栈=[1,2,3,4], 栈顶4=4, 弹出→栈=[1,2,3], pop_index=1
继续检查, 栈顶3≠5
压入5, 栈=[1,2,3,5], 栈顶5=5, 弹出→栈=[1,2,3], pop_index=2
继续检查, 栈顶3=3, 弹出→栈=[1,2], pop_index=3
继续检查, 栈顶2=2, 弹出→栈=[1], pop_index=4
继续检查, 栈顶1=1, 弹出→stack=[], pop_index=5

栈为空，返回True