📃 题目描述

题目链接：

• 703. 数据流中的第 K 大元素 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 剑指 Offer II 059. 数据流的第 K 大数值 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

请实现 KthLargest 类：

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

示例：

输入：
["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);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

🔔 解题思路

如果能够找出 k 个最大的数字，那么第 k 大的数字就是这k个最大数字中最小的一个。

例如，从数据流中已经读出了 4、5、8、2、3 这 5 个数字，其中最大的3个数字是 4、5、8。这3个数字的最小值4就是4、5、8、2、3 这 5 个数字中的第3大的数字。

由于每次都需要找出k个数字中的最小值，因此可以把这k个数字保存到最小堆中。每当从数据流中读出一个数字，就先判断这个新的数字是不是有必要添加到最小堆中:

• 如果最小堆中元素的数目还小于k，那么直接将它添加到最小堆中
• 如果最小堆中已经有k个元素，那么将其和位于堆顶的最小值进行比较:
  • 如果新读出的数字小于或等于堆中的最小值，那么堆中的k个数字都比它大，因此它不可能是k个最大的数字中的一个，由于只需要保存最大的k个数字，因此这个新读出的数字可以忽略
  • 如果新的数字大于堆顶的数字，那么堆顶的数字就是第k+1大的数字，可以将它从堆中删除，并将新的数字添加到堆中，这样堆中保存的仍然是到目前为止从数据流中读出的最大的k个数字，此时第k大的数字正好位于最小堆的堆顶。

其实一句话就能说明白，维护一个小顶堆，堆顶一定是堆中的最小元素

• 如果新添加的元素 < 堆顶，那么就没有添加的必要了
• 如果新添加的元素 > 堆顶，那么去掉堆中的最小元素也就是堆顶，加入新元素

class KthLargest {

    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        // 构造小顶堆存储前 k 大元素
        for (int num : nums) {
            add(num);
        }
    }
    
    public int add(int val) {
        // 如果最小堆中元素的数目还小于 k，那么直接将它添加到最小堆中
        if (minHeap.size() < k) {
            minHeap.offer(val);
        }
        // 如果最小堆中已经有k个元素，那么将其和位于堆顶的最小值进行比较。
        // 如果新的数字大于堆顶的数字，那么堆顶的数字就是第 k + 1 大的数字，可以将它从堆中删除，并将新的数字添加到堆中，这样堆中保存的仍然是到目前为止从数据流中读出的最大的 k 个数字，此时第 k 大的数字正好位于最小堆的堆顶
        else {
            if (val > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(val); // 这里 offer 并不是直接放在堆顶或者堆尾哦，而是内部会进行调整
            }
            // else if (val < minHeap.peek()) 
            // 如果新读出的数字小于或等于堆中的最小值，没有插入的必要
            // 因为堆中的 k 个数字都比 val 大，因此 val 不可能是 k 个最大的数字中的一个
        }
        return minHeap.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

💥 复杂度分析

• 空间复杂度：O(k), 需要使用优先队列存储前 k 大的元素。
• 时间复杂度：O(logk)