Kth Largest Element in a Stream
一个整数流以 nums 中的值开始。随后，adds 中的值会逐个到达。每次有新值到达后，都记录目前为止所有值中第 k 大的值，相同的值分别计数。按顺序返回记录的值，每个 adds 中的值对应一个记录。
nums 至少包含 k-1 个值，因此第一个值到达后，始终至少有 k 个值可供选择。
函数
- kinteger
- 要报告的排名，1 表示最大值
- numsinteger-array
- 流中已有的值
- addsinteger-array
- 按顺序到达的值
- 返回值integer-array
- 每次有新值到达后的第 k 大值
约束条件
1 ≤ nums.length ≤ 1041 ≤ adds.length ≤ 1041 ≤ k ≤ nums.length + 1-104 ≤ nums[i], adds[i] ≤ 104nums可以按任意顺序排列，相同的值会分别计数。
示例
- 输入
- k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
- 输出
- [3, 5, 6, 6, 7]
- 解释
- 3 后面是 7、5、3 和 1 中第三大的数，也就是 3。然后，9 将它提升到 5，6 将它提升到 6，2 没有改变结果，8 将它提升到 7（9、8、7）。
- 输入
- k = 1nums = [-2]adds = [-5, 0, -1, 4]
- 输出
- [-2, 0, 0, 4]
- 解释
- 当
k = 1时，答案是目前为止的最大值：在 0 出现之前是 -2，出现 0 后仍是 0，接着变为 4。
- 输入
- k = 4nums = [6, 6, 2]adds = [6, 1, 9]
- 输出
- [2, 2, 6]
- 解释
- 第一个到达的值产生了 4 个值：6、6、6 和 2，因此第四大的值是 2，1 不会改变它。加入 9 后，最大的 4 个值是 9、6、6 和 6：每个 6 都计入。
进阶
如果也可以从数据流中移除值，你会如何回答同一个问题？
提示
逐个打开提示，每个都会多透露一点。
每次有新值到来后都对所有内容排序，虽然能得到正确答案，但每次都会几乎把所有工作重做一遍。哪些值之后仍有可能成为第
k大的值？值只会不断出现，不会消失。一旦某个值上方出现了
k个更大的值，它就再也不可能成为答案。你只需要保留目前为止见过的最大的k个值。将这
k个值保存在最小堆中。堆顶是其中最小的值，也就是整体中第k大的值。每当有新值到来，如果堆中的值少于k个，就将新值推入堆中；之后，只有当新值更大时，才替换堆顶。
题解
值不会离开数据流，因此低于当前第 k 大的值就会被永久淘汰。只在最小堆中保留最大的 k 个值：堆顶就是答案，每个新值到来时需要进行一次比较，并且最多进行一次 O(log k) 的堆更新。
每次到达后进行排序
结果正确，但无法在最大的测试中运行完毕
思路
将每个值都保留在列表中。每次添加一个值后，按升序对列表排序，并读取索引 length-k 处的值，按定义它就是第 k 大的值。
每次添加一个值，最多需要对 n + m 个值排序，其中 n 和 m 分别是 nums 和 adds 的长度。两者各有 10^4 个值时，总共大约需要进行 2 × 10^9 次比较。
算法
- 把
nums复制到列表values中。 - 对于
adds中的每个值，将其追加到values中。 - 将
values按升序排序，并记录values[length-k]。 - 返回记录的值。
def kthLargestStream(k, nums, adds):
values = list(nums)
result = []
for x in adds:
values.append(x)
values.sort()
# In increasing order the k-th largest sits k places from the end.
result.append(values[len(values) - k])
return result最大的 k 个值的最小堆
思路
当一个值上方已有 k 个更大的值时，这一点在数据流的后续部分始终成立，因此只需关注目前见过的 k 个最大值。把它们存入最小堆。堆顶是这 k 个最大值中最小的值，也就是整体第 k 大的值。
当 x 到达且堆已满时，将它与堆顶进行比较。如果 x 不比堆顶大，它就不属于最大的 k 个值，堆不变。如果它更大，堆顶就会被移出：用 x 替换它，然后向下调整，时间复杂度为 O(log k)。初始值也采用相同的处理方式，因此 nums 可能比 k 长。
在第一个示例中，处理完 nums 后，堆中有 7、1 和 5，堆顶是 1。值 3 到达后替换 1，新的堆顶 3 就是第一个答案。
算法
- 从一个空的最小堆开始。
- 添加
x：如果堆中少于k个值，就推入x。否则，如果x大于堆顶，就用x替换堆顶，并恢复堆的顺序。 - 用这种方式添加
nums中的每个值。 - 对于
adds中的每个值，将它添加到堆中，并记录堆顶。 - 返回记录的值。
import heapq
def kthLargestStream(k, nums, adds):
# A min-heap of the k largest values so far; heap[0] is the smallest of them.
heap = []
def add(x):
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]:
heapq.heapreplace(heap, x) # drop the top, add x
for x in nums:
add(x)
result = []
for x in adds:
add(x)
result.append(heap[0]) # the k-th largest so far
return result
易错点和边界情况
- 去重。9、6、6、6、2 中最大的 4 个数是 9、6、6 和 6。集合，或跳过已存在值的检查，在第三个示例中会返回 2，而不是 6。
- 先读取答案，再添加元素。当
nums中有k-1个值时，只有第一个元素到达后堆才会满，所以要先添加，再读取堆顶。 - 排序后从错误的一端计数。按升序排列时，第
k大的元素位于索引length-k；索引k-1存放的是第k小的元素。 - 使用默认的堆顺序。C++ 的
priority_queue和 Rust 的BinaryHeap都是最大堆：传入greater<int>，或用Reverse包装值。
常见问题3
为什么要用最小堆，而不用最大堆来查找第 k 大的元素？
最大的 k 个值中最小的那个既是答案，也是新值必须超过的值，而大小为 k 的最小堆会把它保持在堆顶。包含所有值的最大堆会把最大值放在堆顶，因此要找到第 k 个值，就需要在每次有新值到来时弹出 k-1 个值，再把它们放回去。
数据流中的第 K 大元素的时间复杂度是多少？
每个新元素的处理成本为 O(log k)：与堆顶比较一次，并且最多在包含 k 个值的堆中调整一次。从 nums 构建堆的成本为 O(n log k)，因此整个过程的时间复杂度为 O((n + m) log k)，额外空间复杂度为 O(k)。
能用排序列表解决数据流中的第 K 大元素问题吗？
是的。让所有值保持有序，使用二分查找将每个新到的值插入到合适的位置，然后读取从末尾数第 k 个位置的值。查找的复杂度是 O(log n)，但插入后移动值的复杂度是每次新到一个值都需要 O(n)：对于 10^4 个初始值和 10^4 个新到的值，大约需要移动 1.5 × 10^8 次。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def kthLargestStream(k, nums, adds):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
k = 3 nums = [7, 1, 5] adds = [3, 9, 6, 2, 8]
预期输出
[3, 5, 6, 6, 7]