跳到主要内容

LeetCode 703. 数据流中的第 K 大元素

本节目标

将固定容量小根堆改造成可持续更新的数据结构，在每次插入后立即回答第 k 大。

这道题是堆与优先队列解题框架的第三道母题。它与“数组中的第 K 个最大元素”使用相同的不变量，但数据不再一次性给出，而是持续加入，并要求每次加入后立刻回答。

查看原题

题意与约束​

设计一个类：

  • 构造时接收整数 k 和初始数组 nums；
  • 每次调用 add(val)，把 val 加入数据流；
  • 返回当前全部元素中的第 k 大元素。

题目保证查询时数据流中至少有 k 个元素。重复值参与排名，例如 [5, 5, 4] 的第 2 大仍是 5。

为什么不能每次重新排序​

若每次 add 后都把全部历史数据重新排序，随着数据流增长，一次查询的成本也会不断增长，而且此前完成的排序工作被反复重做。

我们真正需要长期保存的仍然只是最大的 k 个元素。其余元素一旦低于当前淘汰线，将来也不会因为更大的新元素到来而重新进入前 k 名，因此可以永久舍弃。

在线维护同一个不变量​

对象内部保存容量为 k 的小根堆。无论处理构造函数中的初始数组，还是后来调用 add 加入新值，都执行同一套更新：

把 val 加入小根堆
如果堆大小超过 k:
    弹出堆顶
返回堆顶

每次更新结束后：

  • 堆中保存截至当前最大的 k 个元素；
  • 堆顶是这些元素中最小的一个；
  • 因而堆顶就是当前第 k 大。

构造过程也必须使用相同更新逻辑。若初始数组很长却全部保留，就破坏了空间只与 k 有关的目标。

一个持续更新的例子​

设 k = 3，初始数组为 [4, 5, 8, 2]，初始化后堆中保留 {4, 5, 8}，堆顶为 4。

操作调整后保留的三个最大元素返回值
add(3){4, 5, 8}4
add(5){5, 5, 8}5
add(10){5, 8, 10}5
add(9){8, 9, 10}8

被淘汰的元素无需保留，因为以后只会加入更多元素，它们不可能重新成为第 3 大。

代码实现​

C++ 和 Python 都把“小根堆 + 容量上限”封装在 KthLargest 类中。构造阶段逐个加入初始元素，add 方法恢复不变量并返回堆顶。

C++17
#include <functional>
#include <queue>
#include <vector>
using namespace std;

class KthLargest {
private:
    int k;
    priority_queue<int, vector<int>, greater<int>> top;

    void addToHeap(int value) {
        top.push(value);
        if (static_cast<int>(top.size()) > k) {
            top.pop();
        }
    }

public:
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (int value : nums) {
            addToHeap(value);
        }
    }

    int add(int val) {
        addToHeap(val);
        return top.top();
    }
};

复杂度分析​

  • 构造时间复杂度：O(n log k)，其中 n 是初始数组长度。
  • 单次 add 时间复杂度：O(log k)。
  • 空间复杂度：O(k)，与数据流累计长度无关。

易错点​

  • 保存全部历史数据，失去在线算法应有的空间优势。
  • 只在 add 中限制堆大小，却没有同样处理初始数组。
  • 返回新加入的值或堆中最大值；正确答案始终是小根堆堆顶。
  • 把第 k 大理解为第 k 个不同值，错误去重。
  • 认为小于当前堆顶的旧元素以后可能重新成为答案。随着新元素加入，前 k 名的门槛只会保持或升高，不会降低。

模式迁移​

离线问题变成数据流问题时，关键是寻找可以在一次更新后快速恢复的不变量。固定容量堆适合持续维护 Top K；如果要持续维护中位数，仅保留一侧的 k 个候选已经不够，需要两个堆共同维护数据的两半。