数据流中的第 K 大元素 图解题解

这道题到底在问什么

KthLargest(3,[4,5,8,2])

add(3), add(5), add(10)

输出

4,5,5

最优解：一步一步想明白

1. 3下面按主解代码逐帧推进：先把「大小为 K 的最小堆」建起来，再看每次 add 如何用 O(log k) 维护「第 K 大」。
2. 4不断 add，每次返回当前第 K 大这是一个数据流问题：数字不断加进来，每加一个就要立刻回答「目前第 K 大是多少」。每次都重新排序太慢，需要一个能动态维护的结构。
3. 5堆里=最大的 K 个；堆顶(最小)=第 K 大诀窍：只留「目前最大的 K 个数」，用一个最小堆装它们。那么这 K 个里最小的(也就是堆顶)，正好就是第 K 大。比它还小的数根本排不进前 K，不用管。
4. 6求「第 K 大」反而用「最小堆」——留住最大的 K 个，看它们当中最小的那个。
5. 7[4,5,8,2] → 留最大 3 个 [4,5,8]初始化：4、5、8、2 都进堆，但只能留 3 个，最小的 2 被弹掉。堆里剩 [4,5,8]，堆顶 4 就是当前第 3 大。
6. 83 < 堆顶 4 → 弹掉，堆顶不变add(3)：先把 3 压进堆，超过 3 个了，弹掉最小的——正好就是刚进来的 3。堆顶还是 4，返回 4。比第 K 大还小的数，进来就被弹，毫无影响。
7. 95 > 堆顶 4 → 弹掉 4，堆顶变 5add(5)：5 压进堆，弹掉最小的 4。堆变成 [5,5,8]，堆顶升到 5，返回 5。一个足够大的数进来，会把旧的最小挤出去、抬高第 K 大。
8. 10push 10、弹最小 5 → 堆顶 5add(10)：10 进堆、弹掉最小的 5，堆变 [5,8,10]，堆顶还是 5。每次操作只做一次 push + 一次 pop，O(log k)，远快过重排。
9. 13记住骨架：拿一个大小恒为 K 的最小堆当「状态」，add 时 push 进去、若超 k 就 pop 掉最小，堆顶就是答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = nums[:]
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)
    def add(self, val):
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

class KthLargest {
    int k;
    priority_queue<int, vector<int>, greater<int>> pq;  // 最小堆
public:
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (int x : nums) add(x);
    }
    int add(int val) {
        pq.push(val);
        if ((int)pq.size() > k) pq.pop();
        return pq.top();
    }
};

class KthLargest {
    int k;
    PriorityQueue<Integer> pq = new PriorityQueue<>();  // 最小堆
    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int x : nums) add(x);
    }
    public int add(int val) {
        pq.offer(val);
        if (pq.size() > k) pq.poll();
        return pq.peek();
    }
}

复杂度

面试官可能追问