题目

编写程序，设计一个 KthLargest 类，实时接收无限长度的数据流输入，并在任意时刻以 O(log K) 复杂度返回整个数据流中排名第 K 大的元素。深入对比使用容量为 K 的小顶堆（Min-Heap）维护前 K 大高分榜，相对于维护全量数据大顶堆在空间与时间复杂度上的巨大优势。

输入格式：无需外部输入（内置数据流测试序列）。

输出格式：输出数据流不断追加时当前第 K 大元素的动态跟踪结果。

数据范围与约定：Top-K 极值流维护、空间限制 O(K)。

思路与算法

1. 以小顶堆求第 K 大的精妙之处
很多初学者直觉是用大顶堆，但维护全量大顶堆需要 O(N log N) 空间与时间。而维持一个容量严格为 K 的小顶堆：堆中仅保留当前最大的 K 个数字，堆顶恰好是这 K 个最大数中“最弱的一个”，即排名第 K 大！

2. 淘汰更新机制
当堆未满 K 个时直接入堆；当堆满 K 个且新元素 val > minHeap.top() 时，将堆顶弹出，将新元素入堆。若 val <= minHeap.top()，说明该数连前 K 名都挤不进，直接 O(1) 丢弃。

3. 极高工程价值
这种 Top-K 极值堆模型被广泛应用于搜索引擎高频热词统计、实时排行榜系统与内存敏感型流式计算中。

完整程序

#include <iostream>
#include <queue>
#include <vector>

class KthLargest {
private:
    int k_;
    // 容量固定为 K 的小顶堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap_;

public:
    KthLargest(int k, const std::vector<int>& nums) : k_(k) {
        for (int val : nums) {
            add(val);
        }
    }

    int add(int val) {
        if (minHeap_.size() < static_cast<size_t>(k_)) {
            minHeap_.push(val);
        } else if (val > minHeap_.top()) {
            minHeap_.pop(); // 淘汰前 K 个数中的最小值
            minHeap_.push(val);
        }
        return minHeap_.top();
    }
};

int main() {
    int k = 3;
    std::vector<int> initNums = {4, 5, 8, 2};
    KthLargest tracker(k, initNums);

    std::cout << "初始化流: {4, 5, 8, 2}, 维护第 " << k << " 大元素\n";
    std::cout << "初始状态第 " << k << " 大: " << tracker.add(3) << " (流入 3)\n";
    std::cout << "追加流入 5  -> 当前第 " << k << " 大: " << tracker.add(5) << "\n";
    std::cout << "追加流入 10 -> 当前第 " << k << " 大: " << tracker.add(10) << "\n";
    std::cout << "追加流入 9  -> 当前第 " << k << " 大: " << tracker.add(9) << "\n";
    std::cout << "追加流入 4  -> 当前第 " << k << " 大: " << tracker.add(4) << "\n";

    return 0;
}

运行示例

输出：

初始化流: {4, 5, 8, 2}, 维护第 3 大元素
初始状态第 3 大: 4 (流入 3)
追加流入 5  -> 当前第 3 大: 5
追加流入 10 -> 当前第 3 大: 5
追加流入 9  -> 当前第 3 大: 8
追加流入 4  -> 当前第 3 大: 8