0703. Kth Largest Element in a Stream

题目信息

题号:

0703

难度:

Easy

主题:

设计、数据流、顺序统计

原题:

LeetCode 0703

重点:

对象状态跨多次 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。