---

0950. 按递增顺序显示卡牌

• 标签：队列、数组、排序、模拟
• 难度：中等

题目链接

• 0950. 按递增顺序显示卡牌 - 力扣

题目大意

描述：

给定一个数组 $A$ 代表牌组。牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。

最初，这些卡牌在牌组里是正面朝下的（即，未显示状态）。

现在，重复执行以下步骤，直到显示所有卡牌为止：

1. 从牌组顶部抽一张牌，显示它，然后将其从牌组中移出。
2. 如果牌组中仍有牌，则将下一张处于牌组顶部的牌放在牌组的底部。
3. 如果仍有未显示的牌，那么返回步骤 1。否则，停止行动。

要求：

返回能以递增顺序显示卡牌的牌组顺序。

答案中的第一张牌被认为处于牌堆顶部。

说明：

• $1 \le A.length \le 10^{3}$。
• $1 \le A[i] \le 10^6$。
• 对于所有的 $i \ne j$，$A[i] \ne A[j]$。

示例：

• 示例 1：

输入：[17,13,11,2,3,5,7]
输出：[2,13,3,11,5,17,7]
解释：
我们得到的牌组顺序为 [17,13,11,2,3,5,7]（这个顺序不重要），然后将其重新排序。
重新排序后，牌组以 [2,13,3,11,5,17,7] 开始，其中 2 位于牌组的顶部。
我们显示 2，然后将 13 移到底部。牌组现在是 [3,11,5,17,7,13]。
我们显示 3，并将 11 移到底部。牌组现在是 [5,17,7,13,11]。
我们显示 5，然后将 17 移到底部。牌组现在是 [7,13,11,17]。
我们显示 7，并将 13 移到底部。牌组现在是 [11,17,13]。
我们显示 11，然后将 17 移到底部。牌组现在是 [13,17]。
我们展示 13，然后将 17 移到底部。牌组现在是 [17]。
我们显示 17。
由于所有卡片都是按递增顺序排列显示的，所以答案是正确的。

解题思路

思路 1：队列模拟

这道题需要逆向思考：从最终的递增顺序反推初始的牌组顺序。

1. 逆向模拟：
   • 将排序后的牌从小到大依次放入结果
   • 模拟逆向操作：如果正向是"抽牌、移底"，逆向就是"放底、移顶"
2. 使用队列：
   • 初始化一个索引队列 $[0, 1, 2, ..., n-1]$
   • 模拟抽牌过程，记录每次抽牌的位置
   • 将排序后的牌按照抽牌顺序放入对应位置
3. 具体步骤：
   • 每次从队列头部取出一个索引（对应抽牌位置）
   • 如果队列不为空，将队列头部的下一个索引移到队列尾部（对应移底操作）

思路 1：代码

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        n = len(deck)
        deck.sort()  # 先排序
        
        # 使用队列模拟索引
        queue = collections.deque(range(n))
        result = [0] * n
        
        for card in deck:
            # 当前卡牌放到队列头部对应的位置
            idx = queue.popleft()
            result[idx] = card
            
            # 如果队列不为空，将下一个索引移到队列尾部
            if queue:
                queue.append(queue.popleft())
        
        return result

思路 1：复杂度分析

• 时间复杂度：$O(n \log n)$，其中 $n$ 是牌的数量。排序需要 $O(n \log n)$，模拟过程需要 $O(n)$。
• 空间复杂度：$O(n)$，需要使用队列存储索引。