Medium

题目描述

给你一个整数数组 deck 表示一副牌，其中每张牌都有一个唯一的整数。第 i 张牌上的整数为 deck[i]。

你可以按你想要的顺序重新排列这副牌。最初，所有卡牌都是正面朝下（未显示）放在一副牌中。

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

  1. 从牌堆顶部取一张牌，显示它，然后将其从牌堆中取出。
  2. 如果牌堆中还有牌，则将牌堆顶部的下一张牌放到牌堆的底部。
  3. 如果仍有未显示的卡牌，则返回步骤 1。否则，停止。

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

注意，答案中的第一个条目被认为是牌堆的顶部。

示例 1：

输入：deck = [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。
由于所有显示的卡牌都是递增顺序，所以答案是正确的。

示例 2：

输入：deck = [1,1000]
输出：[1,1000]

提示：

  • 1 <= deck.length <= 1000
  • 1 <= deck[i] <= 10^6
  • deck 的所有值都是唯一的。

解题思路

这道题要求我们重新排列牌组，使得按照特定的规则显示时能够得到递增序列。我们可以使用逆向思维来解决这个问题。

核心思路：逆向模拟

既然我们知道最终显示的顺序应该是递增的，那么我们可以：

  1. 先将原数组排序，得到目标显示序列
  2. 然后逆向模拟整个过程，从最后一张牌开始，反推出初始排列

逆向过程分析：

  • 正向过程：取顶牌 → 将下一张牌移到底部
  • 逆向过程：将底牌移到顶部 → 放入当前要处理的牌

具体算法：

  1. 对原数组进行排序
  2. 使用队列模拟牌组，从最大的牌开始逆向处理
  3. 对于每张牌（除了第一张），先将队列的最后一个元素移到前面，然后将当前牌插入到队列前面
  4. 最终队列中的顺序就是我们要的初始排列

这种方法的巧妙之处在于，我们通过逆向模拟避免了复杂的正向推导，直接从已知的目标序列反推出初始状态。

代码实现

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        sort(deck.begin(), deck.end());
        deque<int> result;
        
        for (int i = deck.size() - 1; i >= 0; i--) {
            if (!result.empty()) {
                result.push_front(result.back());
                result.pop_back();
            }
            result.push_front(deck[i]);
        }
        
        return vector<int>(result.begin(), result.end());
    }
};

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        deck.sort()
        result = []
        
        for i in range(len(deck) - 1, -1, -1):
            if result:
                result.insert(0, result.pop())
            result.insert(0, deck[i])
        
        return result

public class Solution {
    public int[] DeckRevealedIncreasing(int[] deck) {
        Array.Sort(deck);
        var result = new List<int>();
        
        for (int i = deck.Length - 1; i >= 0; i--) {
            if (result.Count > 0) {
                int last = result[result.Count - 1];
                result.RemoveAt(result.Count - 1);
                result.Insert(0, last);
            }
            result.Insert(0, deck[i]);
        }
        
        return result.ToArray();
    }
}

var deckRevealedIncreasing = function(deck) {
    deck.sort((a, b) => a - b);
    const result = [];
    
    for (let i = deck.length - 1; i >= 0; i--) {
        if (result.length > 0) {
            result.unshift(result.pop());
        }
        result.unshift(deck[i]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²)排序 O(n log n)，逆向模拟 O(n²)（每次插入操作需要 O(n)）
空间复杂度O(n)需要额外的数据结构存储结果