287火车驶入驶出顺序验证问题

题解

要验证火车驶出的顺序是否符合栈的先进后出（FILO）规则，我们可以模拟栈的操作过程。具体步骤如下：

1. 初始化：

   • 创建一个空栈 st，用于模拟休息区。
   • 使用指针 j 来跟踪出栈序列 b 的当前元素。

2. 模拟入栈和出栈：

   • 遍历驶入序列 a，将每个火车编号依次压入栈 st。
   • 每次压入后，检查栈顶元素是否与出栈序列 b 中当前指针 j 指向的元素相同：
     • 如果相同，则弹出栈顶元素，并将指针 j 向后移动一位。
     • 重复此过程，直到栈为空或栈顶元素不再匹配 b[j]。

3. 验证结果：

   • 遍历完成后，如果所有火车都按照出栈序列 b 顺利弹出，即栈 st 为空，则说明出栈序列合法，返回 True。
   • 否则，返回 False，表示出栈序列不合法。

代码实现

def solution(n: int, a: list, b: list) -> bool:
    st = []
    j = 0
    for x in a:
        st.append(x)
        while st and st[-1] == b[j]:
            st.pop()
            j += 1
    return len(st) == 0


if __name__ == '__main__':
    print(solution(3, [1, 2, 3], [1, 2, 3]) == True)
    print(solution(3, [1, 2, 3], [3, 2, 1]) == True)
    print(solution(3, [1, 2, 3], [3, 1, 2]) == False)
    print(solution(4, [4, 3, 2, 1], [2, 1, 3, 4]) == True)

算法复杂度

• 时间复杂度：O(n)，其中 n 是序列的长度。每个火车编号最多被压入和弹出栈一次。
• 空间复杂度：O(n)，用于模拟栈的空间。