LeetCode 950题：逆向思维解决卡牌排序问题

发布时间：2026/10/28 23:40:29

1. 题目解析与解题思路

LeetCode 950题"Reveal Cards In Increasing Order"是一个有趣的数组操作问题。题目要求我们模拟一个特殊的发牌过程：给定一副牌，我们需要按照特定规则重新排列它们，使得当按照以下步骤操作时，最终展示的牌面是递增顺序的：

从牌组顶部取出一张牌，展示它
如果还有牌，将下一张牌移动到底部
重复上述步骤直到所有牌都被展示

这个问题的核心在于逆向思考——我们需要从最终展示的顺序出发，逆向推导出初始的牌组排列。

1.1 问题重述与示例

给定一个数组deck，代表牌组中每张牌的值。我们需要重新排列这些牌，使得当按照上述规则展示时，展示的顺序是严格递增的。

示例：输入：[17,13,11,2,3,5,7] 输出：[2,13,3,11,5,17,7]

解释：展示顺序为：2,3,5,7,11,13,17（递增顺序）

1.2 解题思路分析

解决这个问题的关键在于逆向思维。我们可以这样思考：

首先将原始数组排序，得到最终展示的顺序
然后逆向模拟发牌过程，构建初始牌组

具体步骤：

对原始数组进行排序
初始化一个双端队列（或列表）来模拟牌组
从排序后的数组末尾开始，逆向执行发牌操作： a. 如果队列不为空，将队列底部的牌移到顶部 b. 将当前牌放到队列顶部
最终队列中的顺序就是我们要的初始排列

2. 代码实现与优化

2.1 基础实现（Python）

from collections import deque def deckRevealedIncreasing(deck): deck.sort() n = len(deck) result = deque() for i in range(n-1, -1, -1): if result: result.appendleft(result.pop()) result.appendleft(deck[i]) return list(result)

2.2 内存优化技巧

题目中提到"内存100"，意味着我们需要关注内存使用情况。以下是几个优化点：

使用双端队列（deque）而不是普通列表，因为deque在两端操作的时间复杂度都是O(1)
原地排序，避免创建额外的排序数组
可以进一步优化为使用固定大小的数组和指针操作，减少对象创建

优化后的实现：

from collections import deque def deckRevealedIncreasing(deck): deck.sort() n = len(deck) result = deque() for card in reversed(deck): if result: result.appendleft(result.pop()) result.appendleft(card) return list(result)

2.3 时间复杂度分析

排序：O(n log n)
逆向模拟：O(n)
总体时间复杂度：O(n log n)
空间复杂度：O(n)（用于存储结果）

3. 详细步骤解析

3.1 逆向模拟过程详解

让我们用示例[17,13,11,2,3,5,7]来详细说明逆向过程：

排序后得到：[2,3,5,7,11,13,17]
从后向前处理：
- 处理17：队列 -> [17]
- 处理13：先将17移到底部（无变化），然后加入13 -> [13,17]
- 处理11：将17移到顶部 -> [17,13]，然后加入11 -> [11,17,13]
- 处理7：将13移到顶部 -> [13,11,17]，然后加入7 -> [7,13,11,17]
- 处理5：将17移到顶部 -> [17,7,13,11]，然后加入5 -> [5,17,7,13,11]
- 处理3：将11移到顶部 -> [11,5,17,7,13]，然后加入3 -> [3,11,5,17,7,13]
- 处理2：将13移到顶部 -> [13,3,11,5,17,7]，然后加入2 -> [2,13,3,11,5,17,7]

3.2 为什么逆向模拟有效

正向展示的过程是：

取出顶部牌
将新顶部牌移到底部

逆向过程则是：

将底部牌移到顶部
放入新牌到顶部

这种对称性保证了逆向操作能够正确重建初始排列。

4. 常见问题与调试技巧

4.1 边界情况处理

空输入：应返回空列表
单元素输入：直接返回该元素
所有元素相同：任何排列都满足条件，但题目要求严格递增，所以这种情况不会出现

4.2 调试技巧

当你的代码不能通过测试用例时：

手动模拟小例子（n=3或4）
打印中间结果，检查逆向操作是否正确
特别注意索引处理，尤其是在逆向遍历时

4.3 内存使用优化验证

可以使用Python的memory_profiler来验证内存使用：

from memory_profiler import profile @profile def deckRevealedIncreasing(deck): # 实现代码 pass

运行后会显示内存使用情况，帮助我们确认是否达到了"内存100"的要求。

5. 扩展思考与类似题目

5.1 类似题目推荐

LeetCode 239. Sliding Window Maximum（滑动窗口最大值）
LeetCode 622. Design Circular Queue（设计循环队列）
LeetCode 641. Design Circular Deque（设计双端循环队列）

5.2 实际应用场景

这种类型的题目在实际中有多种应用：

卡牌游戏逻辑实现
数据流处理中的缓冲管理
操作系统中的进程调度算法

5.3 算法选择思考

为什么选择双端队列而不是其他数据结构？

我们需要频繁在两端进行操作
普通列表在头部插入是O(n)时间复杂度
链表虽然两端操作是O(1)，但Python中没有内置链表结构
双端队列在Python中由collections模块提供，底层实现高效

6. 不同语言实现对比

6.1 Java实现

public int[] deckRevealedIncreasing(int[] deck) { Arrays.sort(deck); int n = deck.length; Deque<Integer> result = new LinkedList<>(); for (int i = n - 1; i >= 0; i--) { if (!result.isEmpty()) { result.addFirst(result.removeLast()); } result.addFirst(deck[i]); } int[] output = new int[n]; int i = 0; for (int num : result) { output[i++] = num; } return output; }

6.2 C++实现

#include <vector> #include <deque> #include <algorithm> using namespace std; vector<int> deckRevealedIncreasing(vector<int>& deck) { sort(deck.begin(), deck.end()); deque<int> dq; for (int i = deck.size() - 1; i >= 0; i--) { if (!dq.empty()) { dq.push_front(dq.back()); dq.pop_back(); } dq.push_front(deck[i]); } return vector<int>(dq.begin(), dq.end()); }

6.3 JavaScript实现

function deckRevealedIncreasing(deck) { deck.sort((a, b) => a - b); const result = []; while (deck.length) { if (result.length) { result.unshift(result.pop()); } result.unshift(deck.pop()); } return result; }