数组中第 K 个最大元素 图解题解

第 k 大到底指什么

题目要的是把数组降序排列后第 k 个位置上的值，重复的数照常计数，不是第 k 个不同的值。以示例 [5,2,8,1,9,3,7,4,6]、k 取 3 为例，降序前三名是 9、8、7，第 3 大就是 7。理解这一点后，问题可以重述成：从 n 个数里挑出最大的 k 个，报出其中垫底的那一个。

为什么不直接排序取第 k 个

整体排序当然能做：排完取相应下标，时间 O(n log n)。但它做了多余的工作——我们只关心最大的 k 个数是谁，排序却把全部 n 个数的相对顺序都理清楚了，k 远小于 n 时浪费明显。更要命的是排序要求一次拿到全部数据：如果数是流式一个个到来的，排序无从下手，而堆法只需要随来随处理。

求第 k 大为什么用小根堆而不是大根堆

这是全题最反直觉的一步。我们要维护的集合是「目前最大的 k 个数」，而这个集合的门槛，是它内部最小的那个元素——新数只有超过门槛，才有资格挤进来。小根堆恰好把最小值放在堆顶，门槛随手可查、可换。若改用大根堆，堆顶是 k 个里最大的，门槛沉在堆底，判断「新数该不该进」反而没法一步完成。求第 k 大配小根堆、求第 k 小配大根堆，方向记反是本题最高频的错误。

换顶规则为什么能保证答案正确

算法全程维持一条不变量：堆里装的永远是已扫过元素中最大的 k 个。新数到来分两种情况：它不大于堆顶，说明连当前门槛都过不了，绝无可能进入前 k，直接丢弃，堆不动；它比堆顶大，说明原堆顶已经保不住前 k 的席位，弹掉堆顶、放入新数、下沉调整。两种分支处理后不变量都完好，于是扫完全部 n 个数时，堆里正是全局最大的 k 个，堆顶即答案。

复杂度、快速选择与常见坑

每个数至多触发一次 O(log k) 的堆操作，总时间 O(n log k)，堆本身只占 O(k) 空间。另一条路线是快速选择（quickselect）：借快排的 partition 平均 O(n) 定位第 k 大，但最坏退化到 O(n²)，且需要全量数据在手；堆法稳定、好写、天然适配数据流场景，LC703 数据流中的第 K 大就是同一套思路的流式版。两个常见坑：把整个数组不设上限地塞进堆，复杂度退化成 O(n log n)；新数不超过堆顶时也去入堆替换，纯属无效操作还会挤错元素。

Python

import heapq
def findKthLargest(nums, k):
    h = []                       # 小根堆
    for x in nums:
        if len(h) < k:
            heapq.heappush(h, x)      # 没满直接放
        elif x > h[0]:
            heapq.heapreplace(h, x)   # 比堆顶大→换顶
        # 否则丢弃
    return h[0]                  # 堆顶即第 k 大

Java

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> h = new PriorityQueue<>(); // 小根堆
    for (int x : nums) {
        if (h.size() < k) h.offer(x);        // 没满直接放
        else if (x > h.peek()) {             // 比堆顶大
            h.poll(); h.offer(x);            // 换顶
        }
    }
    return h.peek();             // 堆顶即第 k 大
}

C++

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> h; // 小根堆
    for (int x : nums) {
        if ((int)h.size() < k) h.push(x);    // 没满直接放
        else if (x > h.top()) {              // 比堆顶大
            h.pop(); h.push(x);              // 换顶
        }
    }
    return h.top();             // 堆顶即第 k 大
}