LeetCode LCR 059. 数据流中的第 K 大元素

2026-03-28 HGNULB 约 5 分钟

文章信息 5 个分类 7 个标签

分类

LeetCode 简单 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 059. 数据流中的第 K 大元素

题意分析

构造时给定 k 和初始数字，之后每次 add 加入一个新值，并返回整个数据流的第 k 大。相同数值的多次出现分别计数，不能先去重。

题目保证真正查询第 k 大时，数据流已有至少 k 个元素。数据只增加、不删除，因此只保留当前最大的 k 个值就足够了。

解法：固定容量小根堆

核心思路

[!blue]

将问题改写为“最大的 k 个值中，最小的是多少”。用小根堆保存这 k 个候选，堆顶正好就是第 k 大，也是新值到来时需要比较的边界。

堆还未满时，所有已见元素都需要保留，直接插入新值。堆满后，若新值大于堆顶，就删除堆中最小值并加入新值；若新值不大于堆顶，原堆中已经有 k 个值不小于它，保留原堆即可。

被丢弃的值不会改变之后的第 k 大：当前已有 k 个不小于它的值，而这些值之后不会消失。若新值恰好等于堆顶，不替换也会保留相同的前 k 大数值及其重数，因此答案不变。

每次处理后，堆都保存已见元素中最大的 min(k, 已见数量) 个，重复值仍按多个元素存在。元素足够时，查看堆顶即可返回答案，不能把堆顶从结构中移走。

构造函数复用 add 处理初始数组，只使用它的堆维护效果，忽略返回值。初始阶段即使尚不足 k 个，也能逐步填充候选；对外查询时再依赖题目保证的元素数量。

解题步骤

保存 k，建立空小根堆，将初始数字逐个交给 add 处理。

add 时，若堆未满，直接加入新值。

堆已满且新值更大时，弹出堆顶并加入新值；否则保持原堆。

返回堆顶但不删除它，继续保留候选供下一次调用使用。

代码实现

class KthLargest {
    private final int k;
    private final PriorityQueue<Integer> heap;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        heap = new PriorityQueue<>();

        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        if (heap.size() < k) {
            heap.offer(val);
        } else if (val > heap.peek()) {
            // 堆中只保留当前最大的 k 个数，堆顶就是第 k 大。
            heap.poll();
            heap.offer(val);
        }

        return heap.peek();
    }
}

import (
    "container/heap"
)

type IntHeap struct {
    data []int
}

func (h IntHeap) Len() int {
    return len(h.data)
}

func (h IntHeap) Less(i int, j int) bool {
    return h.data[i] < h.data[j]
}

func (h IntHeap) Swap(i int, j int) {
    h.data[i], h.data[j] = h.data[j], h.data[i]
}

func (h *IntHeap) Push(x any) {
    h.data = append(h.data, x.(int))
}

func (h *IntHeap) Pop() any {
    val := h.data[len(h.data)-1]
    h.data = h.data[:len(h.data)-1]
    return val
}

type KthLargest struct {
    k    int
    heap IntHeap
}

func Constructor(k int, nums []int) KthLargest {
    kth := KthLargest{k: k, heap: IntHeap{}}
    heap.Init(&kth.heap)
    for _, num := range nums {
        kth.Add(num)
    }
    return kth
}

func (this *KthLargest) Add(val int) int {
    if this.heap.Len() < this.k {
        heap.Push(&this.heap, val)
    } else if val > this.heap.data[0] {
        // 堆中只保留当前最大的 k 个数，堆顶就是第 k 大。
        heap.Pop(&this.heap)
        heap.Push(&this.heap, val)
    }
    return this.heap.data[0]
}

复杂度分析

设初始数组长度为 m。

时间复杂度：构造为 $O(m\log(k+1))$。单次 add 最坏为 $O(\log(k+1))$，最多进行常数次堆调整；直接丢弃新值时为 $O(1)$。

空间复杂度：$O(k)$，堆最多保留 k 个元素，不随整个数据流持续增长。

关键点总结

[!green]

第 k 大等于前 k 大候选中的最小值，所以使用小根堆。

丢弃较小值的依据是数据只增不减，已经存在的较大候选不会消失。

相同值的不同出现分别计数，比较边界不能解释成恰好有 k-1 个严格更大的值。

易错点总结

[!yellow]

先去重再维护堆：改变了排序后第 k 个元素的定义。

堆中保存最小的 k 个值：方向相反，本题应保留最大的 k 个。

新值较小时仍替换堆顶：会丢掉应保留的更大候选。

返回时弹出堆顶：会破坏下一次调用所需的候选集合。

用固定的 0 代替空堆状态：数据可以为负，是否填满应由堆大小判断。

相似题目

题目	难度	关联与区别
215. 数组中的第K个最大元素	中等	原题一次性求数组第k大，本题持续加入数据，需要维持大小k的小顶堆。
295. 数据流的中位数	困难	同样动态查询排名边界，中位数位置随总数变化，需要维护两半而不是固定k项。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/46051006

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！