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

Categories:

题目描述
思路分析
1. 解法一：模拟 + 队列逆推（推荐）
相似题目

题目描述

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

思路分析

解法一：模拟 + 队列逆推（推荐）

核心思路：

对牌组排序后，利用队列逆向推导每张牌在原始牌堆中的位置

先将索引 [0, n-1] 加入队列，模拟发牌过程：每次取队首索引作为当前位置，将最小的牌放在该位置；然后将队首再次取出，将其加入队尾（模拟翻到底部）

按排序后的顺序依次填充结果数组

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示牌的数量，主要来自排序

空间复杂度：O(n)，队列存储 n 个索引

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

        // 使用队列模拟索引分配
        Deque<Integer> indexQueue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            indexQueue.offer(i);
        }

        int[] result = new int[n];

        // 将排序后的牌依次放置到对应位置
        for (int card : deck) {
            // 队首索引对应当前要放置的位置
            result[indexQueue.poll()] = card;

            // 将下一个索引移到队尾，模拟翻牌操作
            if (!indexQueue.isEmpty()) {
                indexQueue.offer(indexQueue.poll());
            }
        }

        return result;
    }
}

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

    // 使用队列存储索引
    indexQueue := make([]int, n)
    for i := 0; i < n; i++ {
        indexQueue[i] = i
    }

    result := make([]int, n)

    // 将排序后的牌依次放置到对应位置
    for _, card := range deck {
        // 队首索引对应当前要放置的位置
        result[indexQueue[0]] = card
        indexQueue = indexQueue[1:]

        // 将下一个索引移到队尾，模拟翻牌操作
        if len(indexQueue) > 0 {
            indexQueue = append(indexQueue, indexQueue[0])
            indexQueue = indexQueue[1:]
        }
    }

    return result
}

相似题目

题目	难度	考察点
649. Dota2 参议院	中等	队列、贪心、模拟
933. 最近的请求次数	简单	队列、模拟
622. 设计循环队列	中等	队列、设计
1670. 设计前中后队列	中等	队列、设计
2073. 买票需要的时间	简单	队列、模拟

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/37176575