0703. Kth Largest Element in a Stream¶
题目信息¶
- 题号:
0703
- 难度:
Easy
- 主题:
设计、数据流、顺序统计
- 原题:
- 重点:
对象状态跨多次
add调用持续保留;返回的是当前全部元素按非递增顺序排列后的第k个元素,重复值按各次出现分别参与排名
题目重述¶
实现 KthLargest 类,用于持续接收整数并查询当前数据流中的第 k 大元素。
构造函数 KthLargest(k, nums) 接收正整数 k 和初始整数数组 nums。之后每次调用 add(val) 时,都把 val 加入该对象维护的数据流,并返回截至本次调用为止所有初始元素和新增元素中的第 k 大值。这里的“第 k 大”是把所有元素按从大到小排列后位于第 k 个位置的值,重复元素不会去重。
nums 的长度在 [0, 10^4] 范围内,1 <= k <= nums.length + 1;初始元素和后续加入的值均在 [-10^4, 10^4] 范围内,add 最多调用 10^4 次。对象必须在多次调用之间保留此前加入的全部值所形成的状态。
自建示例¶
重复值参与排名:
输入:
操作 = ["KthLargest", "add", "add", "add"]
参数 = [[2, [4,1,4]], [3], [5], [6]]
输出:[null, 4, 4, 5]
解释:初始化后加入 3,序列降序为 [4,4,3,1],第 2 大是 4;加入 5 后为 [5,4,4,3,1],第 2 大仍是 4;加入 6 后为 [6,5,4,4,3,1],第 2 大变为 5。
初始数据流为空:
输入:
操作 = ["KthLargest", "add", "add"]
参数 = [[1, []], [-2], [-5]]
输出:[null, -2, -2]
解释:第一次加入 -2 后它是当前最大值;再加入 -5 后,当前最大值仍为 -2。