LeetCode 950. 按递增顺序显示卡牌

2021-05-19 HGNULB 约 10 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 950. 按递增顺序显示卡牌

题意分析

给一副牌 deck（每张牌的点数互不相同），要求重新排列这副牌，使得按照下面这套固定的揭示规则操作时，揭示出来的点数序列是严格递增的：只要牌堆非空，就取出最上面一张牌揭示，然后如果牌堆还有牌，就把新的最上面一张移到牌堆最底部；如此往复。返回任意一个满足条件的排列（题目保证答案唯一）。

要抓住的第一件事是：揭示规则是给定的、不可改变的，我们能决定的只有初始牌堆的摆放顺序。所以这不是模拟题里常见的「按规则跑一遍」，而是一个反推问题——已知输出序列必须是排序后的 deck，已知过程规则，求输入。

第二件事是揭示规则本身与牌的点数完全无关。取顶、揭示、再把下一张挪到底，这套动作只依赖牌堆里还剩多少张牌以及它们的位置，跟每张牌写着什么数字毫无关系。这条观察是解题的关键：位置的揭示顺序可以脱离点数单独算出来。

既然揭示序列必须递增，而揭示顺序的位置序列又可以独立确定，那么把两者对齐即可——第 1 个被揭示的位置放最小的牌，第 2 个被揭示的位置放第二小的牌，依此类推。这就把「反推排列」变成了「求位置的揭示顺序」加「排序后按序填入」。

约束里 deck 长度不超过 1000，元素互不相同且均为正整数，规模极小，$O(n \log n)$ 绰绰有余，说明本题考的是思路转换而不是效率优化。

边界方面：n = 1 时揭示一张就结束，答案就是原数组；n = 2 时取顶揭示第一张后，牌堆只剩一张，规则里「把顶牌移到底部」在只剩一张时移了等于没移，下一轮直接揭示它——注意这一步不能因为「移动无意义」就跳过判断，代码里必须保证队列为空时不做移动操作。

解法：排序 + 队列模拟位置

核心思路

先看暴力：既然要找一个排列使得揭示序列递增，最直接的想法是枚举 deck 的所有排列，对每个排列按规则模拟一遍看结果是否递增。这是 $O(n! \cdot n)$，n 到 10 就已经不可行。

瓶颈在于把「牌的摆放」当成一个整体去猜。但上一节已经点明：揭示规则只关心位置，不关心点数。所以正确的切入点是把「点数」和「位置」解耦——先算清楚下标 0..n-1 被揭示的先后顺序，再把排好序的点数按这个顺序填进去。

于是引入一个队列，队列里存的不是牌，而是答案数组的下标。初始时队列为 [0, 1, 2, ..., n-1]，含义是：如果按当前顺序摆放，下标 0 在最上面、下标 n-1 在最下面。现在用这个队列正向模拟一遍揭示过程：

队首出队，得到 idx，说明「下标 idx 这个位置是本轮被揭示的」；

若队列仍非空，再把新的队首出队并压回队尾，对应规则里「把下一张顶牌移到底部」。

维持的不变量是：队列从头到尾始终等于「牌堆从上到下各个位置在答案数组中的下标」。初始时这显然成立；每一轮出队一个（对应那张牌被揭走）、把新队首挪到队尾（对应那张牌被移到底部），两个操作恰好复刻了规则对牌堆的改动，所以不变量得以保持。

与此同时，把 deck 升序排序，第 k 轮出队得到的 idx 就是「第 k 小的牌应该被放置的位置」，于是执行 answer[idx] = sortedDeck[k]。全部轮次结束后，answer 就是所求排列——因为按它摆牌再走一遍规则，第 k 轮揭示到的正是位置 idx，而那里放的就是第 k 小的牌，揭示序列自然递增。

这个「用队列模拟位置而非模拟数据」的转换是本题的全部难点。想通之后，代码只是把规则原样抄进循环。

解题步骤

升序排序 deck：揭示序列必须递增，所以第 k 次揭示的一定是第 k 小的牌，排序把「第 k 小」变成「下标 k」，可以顺序取用。为什么可以直接原地排序：题目只要求返回一个合法排列，不要求保留输入顺序。

初始化下标队列为 [0, 1, ..., n-1]：队列元素的语义必须钉死为「答案数组中的位置下标」，而不是牌值。初始顺序即为「牌堆自顶向下」的位置顺序。

按第 k 小的牌依次循环：每轮先 idx = queue.poll()，再 answer[idx] = card。为什么出队即可确定位置：出队的语义就是「这张位置上的牌本轮被揭示」，而本轮揭示的必须是当前最小的未用牌。

若队列非空，把新队首挪到队尾：queue.offer(queue.poll())。为什么必须先判非空：当牌堆被揭到只剩 0 张时，规则里没有「移动」这一步；不判空在 Java 里会对空队列 poll 得到 null 并触发拆箱空指针，在 Go 里会索引越界 panic。

为什么移动的是「揭示之后的新顶牌」而不是被揭示的那张：规则的原文是先揭示顶牌（这张牌离开牌堆），再把此时的顶牌移到底部。所以两次 poll 作用在不同的牌上——第一次的牌永久离开，第二次的牌回到队尾。把顺序写反会让刚被揭示的牌重新入队，位置全乱。

返回 answer：每个下标恰好出队一次，所以 answer 的每个位置都被赋值恰好一次，不会有空洞。

以 deck = [17,13,11,2,3,5,7] 走一遍。排序后为 [2,3,5,7,11,13,17]，n = 7，队列初始 [0,1,2,3,4,5,6]。
第 1 轮：出队 0，answer[0] = 2；队列剩 [1,2,3,4,5,6]，非空，把 1 挪到队尾 → [2,3,4,5,6,1]。
第 2 轮：出队 2，answer[2] = 3；队列 [3,4,5,6,1]，把 3 挪到队尾 → [4,5,6,1,3]。
第 3 轮：出队 4，answer[4] = 5；队列 [5,6,1,3]，把 5 挪到队尾 → [6,1,3,5]。
第 4 轮：出队 6，answer[6] = 7；队列 [1,3,5]，把 1 挪到队尾 → [3,5,1]。
第 5 轮：出队 3，answer[3] = 11；队列 [5,1]，把 5 挪到队尾 → [1,5]。
第 6 轮：出队 1，answer[1] = 13；队列 [5]，把 5 挪到队尾 → 仍是 [5]。
第 7 轮：出队 5，answer[5] = 17；队列已空，跳过移动。
最终 answer = [2,13,3,11,5,17,7]。

反过来验证一下：牌堆自顶向下是 2,13,3,11,5,17,7。揭示 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。揭示序列 2,3,5,7,11,13,17 严格递增，正确。

代码实现

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        int n = deck.length;
        Arrays.sort(deck);

        // 队列里存的是答案数组的下标，代表牌堆自顶向下的位置顺序。
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            queue.offer(i);
        }

        int[] answer = new int[n];
        for (int card : deck) {
            int idx = queue.poll();
            answer[idx] = card;
            // 揭示之后，新的顶牌要挪到底部；牌堆空了则没有这一步。
            if (!queue.isEmpty()) {
                queue.offer(queue.poll());
            }
        }
        return answer;
    }
}

func deckRevealedIncreasing(deck []int) []int {
    n := len(deck)
    sort.Ints(deck)

    // 队列里存的是答案数组的下标，代表牌堆自顶向下的位置顺序。
    queue := make([]int, n)
    for i := 0; i < n; i++ {
        queue[i] = i
    }

    answer := make([]int, n)
    for _, card := range deck {
        idx := queue[0]
        queue = queue[1:]
        answer[idx] = card

        // 揭示之后，新的顶牌要挪到底部；牌堆空了则没有这一步。
        if len(queue) > 0 {
            queue = append(queue, queue[0])
            queue = queue[1:]
        }
    }
    return answer
}

复杂度分析

时间复杂度：$O(n \log n)$。凭什么：排序占 $O(n \log n)$，是主导项；模拟阶段共 n 轮，每轮只做常数次入队出队与一次赋值，合计 $O(n)$，被排序吞掉。

空间复杂度：$O(n)$。凭什么：下标队列最多同时容纳 n 个元素，答案数组固定 n 个位置；排序若用原地实现不额外计入，Java 的 Arrays.sort 对基本类型是原地双轴快排。

关键点总结

当过程规则与数据取值无关时，可以把「模拟数据」换成「模拟位置」——先算出位置的处理顺序，再把排好序的数据按序填进去，这是逆向构造类题目的通用套路。

队列元素的语义必须一次钉死。这题里存的是下标不是牌值，一旦中途混用两种解释，代码就再也说不清楚了。

「反推输入」类题目可以先正向模拟一个与数据无关的骨架，用骨架的输出顺序去对齐排序后的目标序列，避免真的去搜索排列。

规则里「若还有牌才移动」的条件不是可有可无的修饰，它决定了最后一轮的行为，也是空队列崩溃的唯一来源。

面试视角：面试官想听的是「为什么可以用队列存下标」这一步的推理。开口先说「揭示规则只依赖位置不依赖点数，所以位置顺序能独立算出来」，再讲排序对齐，最后才写代码；如果被追问还有没有别的写法，可以提「倒着做」——从最大的牌开始，每次先把队尾元素移到队首再放牌，用双端队列反向还原，是同一思路的镜像。

手写队列时（尤其 Go 用切片模拟），要清楚「取队首」和「弹队首」是两个动作，写反顺序会把同一张牌处理两次。

易错点总结

错误写法：忘记排序直接用原数组 → 用例 deck = [17,13,11,2,3,5,7] 会把 17 放到第一个被揭示的位置，揭示序列以 17 开头，完全不递增。

错误写法：移动前不判断队列是否为空 → 用例 deck = [1] 中第一轮揭示后队列已空，Java 对空 ArrayDeque 调 poll 返回 null，offer(null) 抛空指针；Go 里 queue[0] 直接越界 panic。

错误写法：把被揭示的那张牌重新入队，即写成 idx = queue.poll(); queue.offer(idx); → 用例 [2,3,5,7,11,13,17] 中下标 0 会被反复使用，answer 出现重复赋值和未赋值的空洞，输出含 0。

错误写法：先移动再揭示，把两步顺序颠倒 → 用例 [1,2,3] 得到的位置序列变成 0,2,1 之外的错误序列，反向验证时揭示出的不是递增序列。

错误写法：队列里存牌值而不是下标，试图直接构造答案 → 用例 [17,13,11,2,3,5,7] 中无法知道每张牌该落在答案数组的哪个位置，最后只能再排一次序，逻辑绕回原点。

错误写法：Go 里写成 queue = append(queue[1:], queue[0]) → queue[0] 在切片表达式求值后才取，取到的已是新队首，用例 [1,2,3,4] 会把错误的下标挪到队尾，答案错位。

错误写法：Java 里用 LinkedList 的 remove() 与 add() 混用索引版重载，比如 queue.add(queue.remove(0)) 写成 queue.add(0, queue.remove()) → 用例 [1,2,3,4] 中元素被塞回队首而不是队尾，模拟的是「放到顶部」而非「放到底部」。

错误写法：用 for (int i = 0; i < n; i++) answer[i] = deck[queue.poll()] 这种反向映射 → 用例 [2,3,5,7] 中把「位置」和「第几小」的对应关系用反了，得到的是逆变换，反向模拟不递增。

错误写法：假设 n 为偶数或奇数时行为不同而加特判 → 用例 [1,2] 与 [1,2,3] 都能被同一套逻辑正确处理，多余的特判反而在 n = 2 时提前跳过移动步骤，导致第二张牌位置错误。

错误写法：直接对答案数组做「按规则揭示一遍看是否递增」的校验来搜索排列 → 用例 n = 12 时排列数已达 $4.8 \times 10^8$，超时；这类校验只适合写在本地测试里，不能当解法。

相似题目

题目	难度	考察点
946. 验证栈序列	中等	同样是「给定过程规则判定序列」，但方向是正向校验而非反推初始排列
622. 设计循环队列	中等	考的是队列本身的实现细节与首尾指针环绕，而非用队列去建模问题
225. 用队列实现栈	简单	反复把队首挪到队尾来倒转顺序，和本题的「移到底部」是同一种搬运手法
232. 用栈实现队列	简单	双栈倒腾实现先进先出，练的是均摊分析而不是位置映射
71. 简化路径	中等	典型的按规则线性模拟，规则依赖数据内容，无法像本题那样解耦位置
933. 最近的请求次数	简单	队列作为滑动时间窗，出队条件由数据值决定，与本题的纯位置模拟相反