LeetCode 950. 按递增顺序显示卡牌
题目描述
题意分析
将互不相同的卡牌重新排列，使反复执行“移出并揭示顶牌，再把下一张顶牌移到底部”时，揭示的牌值严格递增。返回的是操作开始前从顶到底的排列，不是已经排好序的揭示结果。
解法：排序 + 队列模拟位置
核心思路
[!blue]
操作每次只按牌堆位置取牌、移牌，完全不比较牌值。因此可以先确定原来哪些位置会依次被揭示，再按这个位置顺序填入从小到大的牌值。
用队列放入答案数组的下标
0到n - 1，队首到队尾表示当前牌堆从顶到底的剩余位置。弹出队首，就得到本轮会揭示的位置；给它填入当前最小的未使用牌值。若队列还没空，再把新的队首移到队尾，模拟下一张顶牌移到底部。队列始终执行与真实牌堆相同的删除和轮转，所以弹出位置的顺序就是最终排列的揭示顺序。第几次弹出就填排序后的第几小牌，所有牌揭示时自然严格递增。每轮恰好确定一个位置，全部
n张牌处理完后，每个位置也恰好填入一次。
解题步骤
- 将输入牌值按升序排序，准备同长度的答案数组。
- 将下标
0到n - 1按顺序加入队列。- 依次取排序后的牌值，弹出队首下标，把当前牌放入答案的这个位置。
- 队列非空时，将新的队首弹出并追加到队尾；空时不再轮转。
- 所有牌处理完后返回答案。只有一张牌时，填入它后队列就为空，同样适用。
代码实现
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;
}
}
import "sort"
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+1))$，排序后队列模拟为线性。
- 空间复杂度：$O(n)$，位置队列和答案数组。
关键点总结
[!green]
- 排序提供应当依次揭示的值，队列提供这些值应放入的原始位置。
- 揭示会永久移除一个位置，轮转只调整剩余位置的顺序。
- 位置模拟与真实操作一致，是填完后揭示顺序正确的依据。
易错点总结
[!yellow]
- 直接把排序数组作为答案，通常无法在轮转操作后仍按递增顺序揭示。
- 不能把刚揭示的位置重新入队，应该轮转揭示后新的队首。
- 先轮转再揭示会改变位置出场顺序，必须遵守题目操作顺序。
- 最后一张牌揭示后队列为空，不能继续读取队首。
- 本实现会对输入
deck排序，原输入顺序不会保留。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 641. 设计循环双端队列 | 中等 | 逆向还原可以用双端队列把末项移到首部，再把当前卡牌插到首部。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！