LeetCode LCR 076. 数组中的第 K 个最大元素 | 走在修行的大街上

走在修行的大街上

2026-03-28 HGNULB 约 14 分钟

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

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

目录

题目描述

✅ LCR 076. 数组中的第 K 个最大元素

题意分析

给定数组 nums 和整数 k，返回数组按降序排列后位于第 k 位的元素。

首先要把题意的一个坑钉死：这里的「第 k 大」是按出现次数排名，不是「第 k 个不同的值」。例如 [3,2,3,1,2,4,5,5,6] 中 k = 4 的答案是 4——降序为 6,5,5,4,...，两个 5 各占一个名次。所以绝对不能去重。

其次要注意题目只索取一个排名位置，并没有要求整个数组有序。直接排序再取下标是 $O(n \log n)$，能过但浪费了大量信息：第 k 位之后的元素之间的相对顺序对答案毫无影响。围绕这一点有两条优化路线。

第一条是只维护 k 个候选。如果手上始终只保留「已扫描元素中最大的 k 个」，扫完之后这批候选里最小的那个就是答案。维护这样一个集合、并能快速找出其中最小值，正是最小堆的职责，代价降到 $O(n \log k)$。

第二条是只递归目标所在的一侧。快速排序的分区操作能把基准值放到它的最终位置上，一次分区之后就能判断目标下标落在哪一侧，另一侧可以整块丢弃。这就是快速选择，平均 $O(n)$。

题目还有一句「请设计并实现时间复杂度为 $O(n)$ 的算法」，这句话是明确在点快速选择。面试中通常先给堆解法拿分，再补快速选择应对追问。

解法一：大小为 k 的最小堆

核心思路

用一个最小堆保存「当前扫描过的元素中最大的 k 个」。选最小堆而不是最大堆是这个解法最容易被记反的地方：因为要淘汰的是候选集里最小的那个，而堆只能 $O(1)$ 看到堆顶，所以堆顶必须是最小值。

遍历数组，每个元素先无条件入堆；若堆的大小超过 k，就弹出堆顶。弹出的是当前候选里最小的那个，它注定挤不进最终的前 k 名。

正确性依赖不变量：每处理完一个元素，堆中恰好是已扫描前缀里最大的 $\min(k, 已扫描数量)$ 个元素。归纳来看，前缀增加一个元素后，新的前 k 大要么就是原来那批，要么是新元素顶替掉原来那批里最小的——两种情况都被「入堆 + 超限弹堆顶」覆盖到了。

扫描结束时堆里是全局最大的 k 个元素，其中最小的那个就是第 k 大，即堆顶。所以最后返回 peek() 而不是 poll() 若干次。

因为题目保证 1 <= k <= nums.length，扫描结束后堆一定恰好有 k 个元素，不必担心堆为空。

解题步骤

建最小堆：Java 的 PriorityQueue 默认就是最小堆，直接用；Go 需要自己实现 heap.Interface 五个方法，Less 里写 h[i] < h[j] 即为最小堆。

遍历数组：对每个元素执行「入堆」。

超限即弹：若堆大小 > k，弹出堆顶。注意是先入后判，不是「先判断再决定是否入堆」——先入堆才能让新元素与原候选里的最小值公平竞争。

返回堆顶：遍历结束后堆顶即第 k 大，用 peek 读取而不要弹出。

以 nums = [3,2,1,5,6,4]、k = 2 走一遍（方括号内为堆中元素集合，堆顶单独标出）：

入 3 → [3]，大小 1 未超限。
入 2 → [2,3]，堆顶 2，大小 2 未超限。
入 1 → [1,2,3]，堆顶 1，大小 3 超限，弹出 1 → [2,3]。
入 5 → [2,3,5]，堆顶 2，超限，弹出 2 → [3,5]。
入 6 → [3,5,6]，堆顶 3，超限，弹出 3 → [5,6]。
入 4 → [4,5,6]，堆顶 4，超限，弹出 4 → [5,6]。

结束时堆为 {5,6}，堆顶 5 即答案。降序排列是 6,5,4,3,2,1，第 2 大确实是 5。

再看重复值用例 nums = [3,2,3,1,2,4,5,5,6]、k = 4：最终堆内是 {4,5,5,6}，堆顶 4 即答案。两个 5 都留在了堆里，各占一个名次——这正是「不能去重」的直接体现。若误用集合去重，候选会变成 {3,4,5,6}，答案错成 3。

代码实现

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                // 堆中始终只保留当前最大的 k 个数，堆顶就是这 k 个数里最小的。
                minHeap.poll();
            }
        }

        return minHeap.peek();
    }
}

type MinHeap []int

func (h MinHeap) Len() int {
    return len(h)
}

func (h MinHeap) Less(i int, j int) bool {
    return h[i] < h[j]
}

func (h MinHeap) Swap(i int, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x any) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() any {
    old := *h
    last := old[len(old)-1]
    *h = old[:len(old)-1]
    return last
}

func findKthLargest(nums []int, k int) int {
    minHeap := &MinHeap{}
    heap.Init(minHeap)

    for _, num := range nums {
        heap.Push(minHeap, num)
        if minHeap.Len() > k {
            // 堆中始终只保留当前最大的 k 个数，堆顶就是这 k 个数里最小的。
            heap.Pop(minHeap)
        }
    }

    return (*minHeap)[0]
}

复杂度分析

时间复杂度：$O(n \log k)$。每个元素入堆一次、最多弹出一次，堆大小恒不超过 k + 1，单次堆操作 $O(\log k)$。当 k 远小于 n 时这明显优于整体排序的 $O(n \log n)$；当 k 接近 n 时两者同阶。

空间复杂度：$O(k)$，堆里只有 k 个候选。这个特性让该解法能处理数据流场景——元素一个个到来、无法全部载入内存时，堆法依然适用，而快速选择必须持有整个数组。

关键点总结

求第 k 大用最小堆，堆顶是候选集里的最小值，也正是要淘汰的对象和最终的答案。这个「大用小、小用大」的对应关系是所有 Top K 题的公共记忆点。

顺序是「先入堆、再判断超限」，让新元素与旧候选公平比较。

不变量：堆中始终是已扫描前缀的前 k 大。理解它就不需要背代码。

最后用 peek 读堆顶，不要 poll。

堆法只需 $O(k)$ 空间且不要求随机访问，是数据流场景下唯一可行的路线。

解法二：三路分区快速选择

核心思路

把「第 k 大」翻译成下标问题：如果把数组整理成降序，答案就在下标 target = k - 1 处。快速选择的目标是只把这一个位置定对，不管其余顺序。

每轮取一个基准值 pivot，对当前区间做降序三路分区，结束后区间被切成三段：[left, greater-1] 都大于 pivot、[greater, less] 都等于 pivot、[less+1, right] 都小于 pivot。

三路（而非常见的两路）分区在本题格外重要。数据里可能有大量重复值，两路分区遇到全相等的数组会退化成每次只切掉一个元素，稳定 $O(n^2)$；三路分区把所有等于 pivot 的元素一次性归位到中段，重复值越多，剩余待处理区间反而越小。

关键性质是：中段的位置已经是最终位置。因为它左边全部更大、右边全部更小，降序排列下它们就该待在那里。于是只需三路判断：target < greater 说明目标在更大的左段，令 right = greater - 1；target > less 说明在更小的右段，令 left = less + 1；否则 target 落在等值中段，nums[target] 就是答案，直接返回。

每轮只进入一侧，丢弃另一侧，这是复杂度能从 $O(n \log n)$ 降到平均 $O(n)$ 的原因：期望每轮规模减半，$n + n/2 + n/4 + \cdots < 2n$。

基准取区间中点元素而非首元素，是为了避免「输入已有序」这种常见退化输入。它仍是确定性策略，理论最坏仍为 $O(n^2)$；若要工程上更稳，可改成随机基准。

解题步骤

目标下标：target = k - 1。因为分区按降序组织，第 k 大就在下标 k - 1。若改成升序分区，目标应是 n - k——两者不能混用，这是本解法最容易写错的一行。

循环搜索：left = 0、right = n - 1，while (left <= right) 反复分区。

三路分区：取 pivot = nums[left + (right - left) / 2]（这样写而非 (left + right) / 2 以避免大数溢出），用三个指针 greater（下一个「大于区」的写入位）、idx（当前考察位）、less（下一个「小于区」的写入位，从右往左）。

nums[idx] > pivot：与 greater 交换，两者同时右移。换过来的元素来自等值区，已检查过，所以 idx 可以安全前进。

nums[idx] < pivot：与 less 交换，只让 less 左移。idx 不能前进——从右侧换过来的元素还没被检查过。

相等：idx 右移即可。

循环条件是 idx <= less，退出时 idx == less + 1，三段划分完成，返回 (greater, less) 作为等值区间。

收缩区间：按 target 与等值区间的关系三路判断，命中则返回 nums[target]。

以 nums = [3,2,1,5,6,4]、k = 2 走一遍，target = 1。

首轮 left=0, right=5，pivot = nums[2] = 1。只有 1 等于基准，其余五个都大于它，分区结束后数组变成 [3,2,5,6,4,1]，大于区占 [0,4]、等值区是 [5,5]。返回 greater = less = 5。target = 1 < 5，目标在更大的左段，令 right = 4。

次轮 left=0, right=4，区间内容 [3,2,5,6,4]，pivot = nums[2] = 5。分区过程：3 小于基准换到右端、4 小于基准再换、6 大于基准归入左侧、2 小于基准换出，结束时数组为 [6,5,2,4,3]，大于区 [0,0]、等值区 [1,1]、小于区 [2,4]。返回 greater = less = 1，target = 1 正落在等值区内，直接返回 nums[1] = 5。

两轮分区就得到答案，全程没有把数组排序。关键在于每轮都能凭「等值区已在最终位置」这一性质做出确定的三路判断，从而整块丢弃另一侧。

再看全相等的极端用例 nums = [2,2,2,2]、k = 3：首轮 pivot = 2，三路分区后大于区与小于区都为空，等值区是整个 [0,3]。target = 2 落在其中，一轮就返回 2。若用两路分区，这个输入会退化成四轮。

代码实现

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int target = k - 1;
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int[] equalRange = partition(nums, left, right);
            if (target < equalRange[0]) {
                right = equalRange[0] - 1;
            } else if (target > equalRange[1]) {
                left = equalRange[1] + 1;
            } else {
                return nums[target];
            }
        }

        return -1;
    }

    private int[] partition(int[] nums, int left, int right) {
        int pivot = nums[left + (right - left) / 2];
        int greater = left;
        int idx = left;
        int less = right;

        while (idx <= less) {
            if (nums[idx] > pivot) {
                // greater 左侧都大于 pivot，等值区间会被留在中间。
                swap(nums, greater, idx);
                greater++;
                idx++;
            } else if (nums[idx] < pivot) {
                swap(nums, idx, less);
                less--;
            } else {
                idx++;
            }
        }

        return new int[] {greater, less};
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

func findKthLargest(nums []int, k int) int {
    target := k - 1
    left := 0
    right := len(nums) - 1

    for left <= right {
        equalLeft, equalRight := partition(nums, left, right)
        if target < equalLeft {
            right = equalLeft - 1
        } else if target > equalRight {
            left = equalRight + 1
        } else {
            return nums[target]
        }
    }

    return -1
}

func partition(nums []int, left int, right int) (int, int) {
    pivot := nums[left+(right-left)/2]
    greater := left
    idx := left
    less := right

    for idx <= less {
        if nums[idx] > pivot {
            // greater 左侧都大于 pivot，等值区间会被留在中间。
            nums[greater], nums[idx] = nums[idx], nums[greater]
            greater++
            idx++
        } else if nums[idx] < pivot {
            nums[idx], nums[less] = nums[less], nums[idx]
            less--
        } else {
            idx++
        }
    }

    return greater, less
}

复杂度分析

时间复杂度：平均 $O(n)$，最坏 $O(n^2)$。每轮分区是 $O(区间长度)$，且只递归一侧，期望规模每轮减半，总量收敛到 $2n$ 以内。最坏情况出现在每轮分区都极度不平衡时；取中点基准能挡住「已排序输入」这类常见构造，但无法排除所有对抗输入，随机基准可把最坏情况的概率压到几乎为零。

空间复杂度：$O(1)$。分区完全原地进行，而且这里写成了迭代收缩区间而非递归，连栈帧都不需要。

注意本解法会原地修改输入数组。如果调用方还要用原数组，需要先拷贝一份，这是它相对堆法的一个隐性代价。

关键点总结

降序分区下第 k 大对应下标 k - 1；若按升序分区则是 n - k。分区方向和目标下标必须成对确定。

三路分区把等值元素一次归位，是应对大量重复值的关键；两路分区在全相等输入上退化为 $O(n^2)$。

「等值中段已在最终位置」是能做三路判断、丢弃另一半的依据。

与右侧交换后 idx 不能前进——换来的元素尚未检查。这是分区代码最高频的 bug。

left + (right - left) / 2 而不是 (left + right) / 2，避免下标之和溢出。

快速选择要求随机访问且会改动原数组，所以不适用于数据流场景。

解法对比

最小堆：$O(n \log k)$ 时间、$O(k)$ 空间，复杂度稳定无退化，代码短、边界少，且不修改输入、支持数据流。是面试中更稳的主解，尤其当 k 远小于 n 时。

快速选择：平均 $O(n)$ 时间、$O(1)$ 空间，是题目「设计 $O(n)$ 算法」那句提示所指向的答案。代价是分区边界易写错、最坏可退化到 $O(n^2)$、会原地打乱输入数组，也无法处理流式数据。

面试建议：先用最小堆快速给出一个正确解并说明「大用小堆」的原因，再主动提出「题目要求 $O(n)$，我可以用快速选择做到平均线性」，并点出三路分区应对重复值、随机基准规避最坏情况这两个细节。能把两者的适用边界（k 的大小、是否允许改动输入、是否流式）讲清楚，比只会写一种更有说服力。

易错点总结

错误写法：先去重再取第 k 大。反例 nums = [3,2,3,1,2,4,5,5,6]、k = 4：按出现次数排序后的第 4 大是 4；去重后再取会得到 3，改变了题目的排名语义。

堆用反了：求第 k 大却用最大堆，堆顶变成最大值，弹出的正是要保留的元素。记住「求最大用最小堆」。

先判断再入堆：写成「堆满了就跳过入堆」会让后来的大元素永远进不来。必须先入堆再弹超限的堆顶。

最后 poll 而不是 peek：虽然本题返回值相同，但把堆弹空后若还要复用堆就出错了；语义上要的是「查看」而非「取出」。

快速选择目标下标写错：降序分区必须用 k - 1。误用 nums.length - k（升序的下标）会得到第 k 小。

三路分区中与右侧交换后前进 idx：换来的元素未经检查，会被直接跳过，分区结果错误。

用两路分区应付重复值：[2,2,2,...,2] 这类输入会退化到 $O(n^2)$ 而超时。

(left + right) / 2 溢出：数组极大时下标之和可能超出 int，应写成 left + (right - left) / 2。

忽略快速选择会改动原数组：如果题目或调用方后续还需要原始顺序，必须先拷贝。

认为排序解法一定不能用：$O(n \log n)$ 的排序加取下标是完全可以通过判题的兜底方案，面试时可以先说它作为基线，再给出优化，但不宜作为最终答案。

相似题目

题目	难度	考察点
347. 前 K 个高频元素	中等	先哈希计数再对「频次」求 Top K，也可用桶排序做到 $O(n)$
703. 数据流中的第 K 大元素	简单	流式场景，只有堆法适用，快速选择在此彻底失效
692. 前K个高频单词	中等	频次相同时按字典序，需要自定义比较器且注意堆的排序方向要取反
973. 最接近原点的 K 个点	中等	求第 K 小，改用最大堆；比较键换成距离平方，避免开方误差
912. 排序数组	中等	手写快排，本题分区逻辑的来源；同样需要三路分区应对重复值
378. 有序矩阵中第 K 小的元素	中等	借助行列有序，可用堆多路归并或对值域二分，Top K 的另一种解法
4. 寻找两个正序数组的中位数	困难	求第 k 小的进阶形态，需要在两个有序数组上二分划分
LCR 060. 前 K 个高频元素	中等	与 347 同题
剑指 Offer 40. 最小的k个数	简单	求最小的 k 个，堆的方向与本题相反，返回整批而非单个
面试题 17.14. 最小K个数	中等	与剑指 Offer 40 同题