题目要求
给定整数数组 nums 和整数 k,返回数组按降序排列后的第 k 大元素。重复值分别占据排名位置,并不是第 k 个不同值。
官方示例
输出:5
输出:4
Unit 06 · LeetCode #703
大小为K的最小堆保存当前最大的K个元素。堆顶是这K个元素中最小的一个,因此恰好是所有已见元素中的第K大。新值到达时,只需更新这一小块候选。
设计一个类,持续维护数据流中按排序顺序计算的第 k 大元素。初始化时给定整数 k 和初始数组 nums;每次调用 add(val) 加入新值,并返回当前全部元素中的第 k 大。
0 ≤ nums.length ≤ 10⁴;1 ≤ k ≤ nums.length + 1;[-10⁴,10⁴];add 最多调用 10⁴ 次。维护大小不超过 k 的最小堆。每次插入后若堆大小超过 k,弹出最小值。初始化可逐个加入,时间 O(n log k);每次 add 为 O(log k),空间 O(k)。
将所有元素按从大到小排列后的第K个位置。重复值需要分别计入,并不是第K个不同值。
堆内始终保存当前最大的K个元素;其他元素已经不可能影响当前第K大边界。
最小堆堆顶是Top-K中最小者,正好把“前K大”和“其余元素”分开。
新值持续到达,无法每次重新完整排序;需要支持增量更新并立即返回答案。
选出三个最大元素后,其中最小者就是整体第三大。
| 降序排名 | 数值 | 所属区域 |
|---|
堆内所有元素构成当前 Top-K;堆外所有已处理元素都不大于堆顶。
Top-K中最应该被淘汰的是最小者。最小堆让这个边界元素始终位于根,插入新值后可在 O(log k) 内淘汰。
每次重新排序会维护大量不会被查询的排名信息;最小堆只保存前K大及其中最小边界。
堆的方向、容量以及“第K大是否去重”都必须由题目定义推导。
堆顶会是第一大;超容量时弹出堆顶反而删除最重要的最大元素。
若保留所有元素,最小堆顶是整体最小值,不再是第K大。
第K大按排序位置计数。示例中的多个7和9都必须分别保留。
题目保证 k ≤ nums.length + 1,因此即使初始数组只有K−1个元素,第一次add后也有足够元素返回第K大。
heappushpop 合并插入与弹出。但基础版本更直接表达不变量。数据从持续到达的流,变成一次性离线数组。变化的是调用方式;不变的是“大小 K 的最小堆保存当前最大的 K 个元素”。
给定整数数组 nums 和整数 k,返回数组按降序排列后的第 k 大元素。重复值分别占据排名位置,并不是第 k 个不同值。
1 ≤ k ≤ nums.length ≤ 10⁵;-10⁴ ≤ nums[i] ≤ 10⁴;k 的最小堆,以复用 #703 的 Top-K 不变量。每次点击你认为的下一步;顺序错误会清空当前排列,但不会显示正确答案。
这里不要求整段代码记忆,而是确认“容器、扫描、候选更新、答案边界”四个角色。
完整运行官方样例后开放。请独立实现,不提供占位符或完整参考答案。
你已经把动态数据流中的Top-K边界迁移到离线数组:调用方式改变,但大小K的最小堆、超容量淘汰最小者和heap[0]的排名语义保持不变。