What is the most efficient data structure to maintain the kth largest element in a stream?

A min-heap of size k efficiently maintains the kth largest element, ensuring O(log k) insertion and O(1) retrieval.

How does the KthLargest class handle initialization with an existing array?

It iterates through the initial array, inserting each element into the min-heap while maintaining a size of k, ensuring the kth largest element is correct from the start.

What should be returned after each add operation?

After adding a new number, return the top of the min-heap, which represents the current kth largest element in the stream.

Can duplicates affect the kth largest result?

Yes, duplicates should be correctly inserted into the min-heap since the kth largest depends on the exact multiset of values.

How does binary-tree traversal relate to this problem?

The pattern of maintaining a min-heap mirrors binary-tree traversal logic, where we track and update hierarchical state to efficiently find the kth largest element.

#703

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

数据流中的第 K 大元素

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。请实现 KthLargest 类： KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。 int add(int val) 将 val…

树设计二叉搜索树堆（优先队列）二叉树

题目描述

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例 1：

输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

输出：[null, 4, 5, 5, 8, 8]

解释：

KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // 返回 4
kthLargest.add(5); // 返回 5
kthLargest.add(10); // 返回 5
kthLargest.add(9); // 返回 8
kthLargest.add(4); // 返回 8

示例 2：

输入：
["KthLargest", "add", "add", "add", "add"]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]

输出：[null, 7, 7, 7, 8]

解释：

KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2); // 返回 7
kthLargest.add(10); // 返回 7
kthLargest.add(9); // 返回 7
kthLargest.add(9); // 返回 8

提示：

0 <= nums.length <= 10⁴
1 <= k <= nums.length + 1
-10⁴ <= nums[i] <= 10⁴
-10⁴ <= val <= 10⁴
最多调用 add 方法 10⁴ 次

lightbulb

解题思路

方法一：优先队列（小根堆）

我们维护一个优先队列（小根堆） $\textit{minQ}$ 。

初始化时，我们将数组 $\textit{nums}$ 中的元素依次加入 $\textit{minQ}$ ，并保持 $\textit{minQ}$ 的大小不超过 $k$ 。时间复杂度 $O(n \times \log k)$ 。

每次加入一个新元素时，如果 $\textit{minQ}$ 的大小超过了 $k$ ，我们就将堆顶元素弹出，保证 $\textit{minQ}$ 的大小为 $k$ 。时间复杂度 $O(\log k)$ 。

这样， $\textit{minQ}$ 中的元素就是数组 $\textit{nums}$ 中最大的 $k$ 个元素，堆顶元素就是第 $k$ 大的元素。

空间复杂度 $O(k)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.min_q = []
        for x in nums:
            self.add(x)

    def add(self, val: int) -> int:
        heappush(self.min_q, val)
        if len(self.min_q) > self.k:
            heappop(self.min_q)
        return self.min_q[0]


# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

speed

复杂度分析

指标	值
时间	complexity is O((M + N) * log k) where N is initial array length and M is number of add calls; each insertion into a size-k min-heap takes O(log k). Space complexity is O(k) to store the min-heap representing the k largest elements.
空间	O(k)

psychology

面试官常问的追问

外企场景

question_mark
Ask about handling large dynamic streams and maintaining a fixed-size tracking structure.
question_mark
Check if the candidate correctly initializes the heap and updates it with each add operation.
question_mark
Probe knowledge of edge cases, such as when the initial array has fewer than k elements.

warning

常见陷阱

外企场景

error
Using a full sorted array each time, leading to O(N log N) insertion time per add.
error
Forgetting to maintain the heap size at exactly k, causing incorrect kth largest results.
error
Not handling duplicate values correctly, which may affect the min-heap top.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Track the kth smallest element in a live data stream instead of the largest.
arrow_right_alt
Support a stream of real numbers or floats instead of integers with the same heap approach.
arrow_right_alt
Allow dynamic updates to k during the stream, requiring heap reconstruction or resizing.

help

常见问题

外企场景

继续练习

#449 序列化和反序列化二叉搜索树 #173 二叉搜索树迭代器 #669 修剪二叉搜索树