950. 按递增顺序显示卡牌

🎯 问题描述

描述：
牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。
最初，这些卡牌在牌组里是正面朝下的（即，未显示状态）。
现在，重复执行以下步骤，直到显示所有卡牌为止：

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

返回能以递增顺序显示卡牌的牌组顺序。答案中的第一张牌被认为处于牌堆顶部。

说明：

这是一个逆向模拟与队列结合的问题。
核心策略：
- 我们知道最终显示的顺序必须是从小到大的（即排序后的 deck）。
- 问题的难点在于：如何安排初始牌序，使得经过“抽一张、移一张到底部”的操作后，刚好能按顺序抽出这些牌？
- 我们可以模拟抽牌的过程，但不是模拟具体的数字，而是模拟卡牌的位置（下标）。
- 按照题目规则，第一个被抽出的位置放最小的数，第二个被抽出的位置放第二小的数，以此类推。
示例：
示例 1：

输入：[17,13,11,2,3,5,7]
输出：[2,13,3,11,5,17,7]
解释：
我们将原数组排序得到 [2,3,5,7,11,13,17]。
我们需要找到一个初始排列，使得：
- 第1次抽出的位置放 2
- 第2次抽出的位置放 3
- 第3次抽出的位置放 5
...以此类推。
通过模拟下标的抽取过程，我们可以确定每个位置应该放哪个数字。

💻 解题思路

思路1：队列模拟下标

核心逻辑

排序：
- 首先将 deck 数组从小到大排序。因为我们最终要按这个顺序依次“填入”到结果数组中。
初始化下标队列：
- 创建一个双端队列 idx，存入 0 到 n-1 的所有下标。这个队列代表了牌组中各个位置的“排队顺序”。
模拟抽牌过程：
- 遍历排序后的 deck，对于每一个数字 num：
  - 抽牌：从队列头部弹出一个下标 idx.popleft()。这个下标就是当前 num 应该放置的位置。将其填入结果数组 ans。
  - 移牌到底部：如果队列不为空，将新的队首下标弹出，并立刻加入队尾 idx.append(idx.popleft())。这完美模拟了题目中“将下一张牌放到底部”的操作。
返回结果：
- 遍历结束后，ans 数组即为所求的初始牌组顺序。

代码实现

from collections import deque
from typing import List

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        n = len(deck)
        # 1. 将卡牌按从小到大排序，准备依次填入
        deck.sort()
        
        # 2. 初始化结果数组和下标队列
        ans = [0] * n
        # 队列中存入 0 到 n-1 的下标，代表牌组中各个位置的排队顺序
        idx = deque(range(n))
        
        # 3. 模拟抽牌和移牌的过程
        for num in deck:
            # 模拟“抽一张牌”：弹出队首下标，将当前最小的数字填入该位置
            ans[idx.popleft()] = num
            
            # 模拟“将下一张牌移到底部”：如果队列还有剩余，将新的队首移到队尾
            if idx:
                idx.append(idx.popleft())
                
        return ans

📊 性能分析

时间复杂度： $O(N \log N)$ $O (N lo g N)$
- 排序的时间复杂度为 $O(N \log N)$ 。
- 后续的遍历和队列操作（每个下标最多入队、出队两次）的时间复杂度为 $O(N)$ 。
- 总体时间复杂度由排序决定，为 $O(N \log N)$ 。
空间复杂度： $O(N)$ $O (N)$
- 需要一个长度为 $N$ 的结果数组 ans。
- 需要一个队列 idx 存储 $N$ 个下标。

思考

为什么要模拟下标而不是数字？
- 如果直接模拟数字，我们需要逆向推导（从结果推初始状态），逻辑比较绕。
- 而模拟下标是一种正向思维：我们虽然不知道初始牌序是什么，但我们知道抽牌的顺序规则是固定的。通过模拟这个规则，我们可以知道“第几个被抽出的位置”是队列里的哪个下标。既然第一个被抽出的位置要放最小的数，那我们就把最小的数填进去，逻辑非常顺畅。
队列的作用：
- 队列完美契合了题目中“循环移动”的特性。popleft() 对应抽牌，append(popleft()) 对应把牌移到底部。这种操作在数组中实现会非常麻烦（需要频繁移动元素），而在队列中都是 $O(1)$ 的操作。
与逆向思维解法的对比：
- 另一种常见的解法是逆向模拟：从最大的数开始，先把队尾的数移到队首，再把当前数放入队首。
- 你的这种“正向模拟下标”的解法在逻辑上更容易理解，因为它直接对应了题目的操作流程，只是把操作对象从“具体的数”换成了“位置”。
边界情况：
- 当队列中只剩最后一个下标时，if idx: 的判断保证了不会执行多余的“移牌”操作，符合题目逻辑（只剩一张牌时直接抽出，无需移动）。