Easy

题目描述

设计一个找到数据流中第 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]

提示：

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

解题思路

这道题要求我们维护一个数据流中的第 k 大元素。关键思路是使用**最小堆（优先队列）**来高效地维护前 k 大的元素。

核心思想：

  • 维护一个大小为 k 的最小堆
  • 堆顶元素就是第 k 大的元素
  • 当堆的大小超过 k 时，移除堆顶（最小元素）

解法分析：

  1. 最小堆解法（推荐）：使用大小为 k 的最小堆，堆顶始终是第 k 大元素。时间复杂度：初始化 O(n log k)，add 操作 O(log k)。

  2. 排序解法：每次 add 后对整个数组排序，然后返回第 k 大元素。时间复杂度较高，不推荐。

  3. 二分查找 + 插入：维护有序数组，使用二分查找插入位置。空间效率不如堆解法。

最小堆解法是最优的，因为我们只需要知道第 k 大的元素，不需要维护所有元素的完整排序。堆的大小固定为 k，空间效率高，且每次操作时间复杂度为 O(log k)。

代码实现

class KthLargest {
private:
    priority_queue<int, vector<int>, greater<int>> minHeap;
    int k;
    
public:
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (int num : nums) {
            minHeap.push(num);
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
    }
    
    int add(int val) {
        minHeap.push(val);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
        return minHeap.top();
    }
};

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        
        while len(self.heap) > k:
            heapq.heappop(self.heap)

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

public class KthLargest {
    private PriorityQueue<int, int> minHeap;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        minHeap = new PriorityQueue<int, int>();
        
        foreach (int num in nums) {
            minHeap.Enqueue(num, num);
            if (minHeap.Count > k) {
                minHeap.Dequeue();
            }
        }
    }
    
    public int Add(int val) {
        minHeap.Enqueue(val, val);
        if (minHeap.Count > k) {
            minHeap.Dequeue();
        }
        return minHeap.Peek();
    }
}

var KthLargest = function(k, nums) {
    this.k = k;
    this.heap = [...nums];
    this.heap.sort((a, b) => a - b);
    
    while (this.heap.length > k) {
        this.heap.shift();
    }
};

KthLargest.prototype.add = function(val) {
    this.heap.push(val);
    this.heap.sort((a, b) => a - b);
    
    if (this.heap.length > this.k) {
        this.heap.shift();
    }
    
    return this.heap[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(n log k)O(k)
addO(log k)O(k)

其中 n 为初始数组长度，k 为要求的第 k 大元素的 k 值。

相关题目