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

Categories:

题目描述
思路分析
1. 解法一：小根堆维护前 K 大（推荐）
相似题目

题目描述

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

思路分析

解法一：小根堆维护前 K 大（推荐）

核心思路：

维护一个大小为 K 的小根堆。

新元素大于堆顶时替换堆顶。

堆顶即为第 K 大元素。

复杂度分析：

时间复杂度：插入 O(log k)，查询 O(1)。

空间复杂度：O(k)，堆大小为 K。

class KthLargest {
    private final PriorityQueue<Integer> heap = new PriorityQueue<>();
    private final int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int v : nums) {
            add(v);
        }
    }

    public int add(int val) {
        if (heap.size() < k) {
            heap.offer(val);
        } else if (val > heap.peek()) {
            heap.poll();
            heap.offer(val);
        }
        return heap.peek();
    }
}

type KthLargest struct {
	k    int
	heap *IntHeap
}

func Constructor(k int, nums []int) KthLargest {
	h := &IntHeap{isMin: true}
	heap.Init(h)
	kl := KthLargest{k: k, heap: h}
	for _, v := range nums {
		kl.Add(v)
	}
	return kl
}

func (k *KthLargest) Add(val int) int {
	if k.heap.Len() < k.k {
		heap.Push(k.heap, val)
	} else if val > k.heap.Top() {
		heap.Pop(k.heap)
		heap.Push(k.heap, val)
	}
	return k.heap.Top()
}

type IntHeap struct {
	data  []int
	isMin bool
}

func (h IntHeap) Len() int { return len(h.data) }
func (h IntHeap) Less(i, j int) bool {
	if h.isMin {
		return h.data[i] < h.data[j]
	}
	return h.data[i] > h.data[j]
}
func (h IntHeap) Swap(i, 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 {
	old := h.data
	n := len(old)
	val := old[n-1]
	h.data = old[:n-1]
	return val
}
func (h IntHeap) Top() int { return h.data[0] }

相似题目

题目	难度	考察点
215. 数组中的第 K 个最大元素	中等	堆
703. 数据流中的第 K 大元素	简单	堆
347. 前 K 个高频元素	中等	堆
295. 数据流的中位数	困难	双堆
239. 滑动窗口最大值	困难	单调队列

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/51429010