验证图书取出顺序

难度: Medium

现在图书馆有一堆图书需要放入书架，并且图书馆的书架是一种特殊的数据结构，只能按照一定的顺序放入和拿取书籍。

给定一个表示图书放入顺序的整数序列 putIn，请判断序列 takeOut 是否为按照正确的顺序拿取书籍的操作序列。你可以假设放入书架的所有书籍编号都不相同。

示例 1：

输入：putIn = [6,7,8,9,10,11], takeOut = [9,11,10,8,7,6]
输出：true
解释：我们可以按以下操作放入并拿取书籍：
push(6), push(7), push(8), push(9), pop() -> 9,
push(10), push(11),pop() -> 11,pop() -> 10, pop() -> 8, pop() -> 7, pop() -> 6

示例 2：

输入：putIn = [6,7,8,9,10,11], takeOut = [11,9,8,10,6,7]
输出：false
解释：6 不能在 7 之前取出。

提示：

0 <= putIn.length == takeOut.length <= 1000
0 <= putIn[i], takeOut < 1000
putIn 是 takeOut 的排列。

注意：本题与主站 946 题相同：https://leetcode-cn.com/problems/validate-stack-sequences/

Submission

运行时间: 60 ms

内存: 15.1 MB

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = list()
        i = 0
        for num in pushed:
            stack.append(num)
            while stack and stack[-1] == popped[i]:
                i += 1
                stack.pop()
        return len(stack) == 0

Explain

这个题解利用了一个栈来模拟书籍放入和拿取的过程。每次循环遍历放入序列，将元素推入栈中，然后检查栈顶元素是否与拿取序列当前指向的元素相同。如果相同，就从栈中弹出这个元素，并将拿取序列的指针向前移动。这个过程重复进行，直到放入序列遍历完成。最后，如果栈为空，则意味着拿取序列可以完全按照给定的顺序从栈中拿出所有书籍，返回true；如果栈不为空，返回false。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []  # 初始化一个空栈
        i = 0  # 初始化拿取序列的索引
        for num in pushed:  # 遍历每个放入的元素
            stack.append(num)  # 将元素放入栈
            while stack and stack[-1] == popped[i]:  # 当栈非空且栈顶元素等于当前拿取元素
                i += 1  # 移动拿取序列的索引
                stack.pop()  # 从栈中弹出元素
        return len(stack) == 0  # 如果栈空了，返回true，否则返回false

Explore

在模拟书籍取出顺序的过程中使用栈，是因为这个问题本质上是一个后进先出（LIFO）的问题。书籍被放入一个容器中，随后按照一定顺序取出，其中最后放入的书籍需要首先被取出。这恰好符合栈的操作特性。如果使用队列（先进先出，FIFO），则无法模拟最后放入的书籍首先被取出的情况。而链表虽然可以在任何位置插入和删除元素，但使用链表进行这种操作会增加额外的复杂度，因为需要追踪链表的特定位置，而栈可以更简单直接地完成所需的操作。

这个循环的作用是检查栈顶元素是否与当前需要被拿取的书籍（即拿取序列中的当前元素）相匹配。如果相匹配，就从栈中移除该元素，并将拿取序列的索引向前移动一位，继续比较下一个元素。这个过程保证了只有当书籍的顺序正确，即栈顶的书籍恰好是下一个需要取出的书籍时，才会从栈中移除。这种方式确保了整个拿取序列可以按照预定的顺序成功地从栈中按后进先出的顺序移除，从而验证拿取顺序的正确性。

如果拿取序列与放入序列的长度不同，理论上这表示输入数据存在问题，因为每本书籍放入后都应该被取出。在实际算法实现中，如果长度不同，算法应该首先验证这一点并返回一个错误或异常。在题解提供的算法中，如果不进行长度比较直接执行，可能会导致索引越界的错误（当尝试访问不存在的拿取序列元素时）。因此，最佳实践是在算法开始时检查两个序列的长度是否相等，若不相等则直接返回false或抛出异常。

在这个算法中，如果在任何时刻栈顶元素与拿取序列当前元素不匹配，该元素不会从栈中被弹出，算法会继续检查放入序列中的下一个元素。只有当所有的元素都被正确匹配并从栈中弹出后，栈最终会变为空，这时算法返回true。如果存在不匹配的情况并且不能通过后续操作解决，栈将不会为空，算法最终将返回false。因此，不存在栈中元素与拿取序列当前元素不匹配但算法还是返回true的情况。