leetcode基础算法108题LeetCode数据流中的第

导读题目设计一个找到数据流中第k大元素的类（class）。注意是排序后的第k大元素，不是第k个不同的元素。请实现KthLargest类：KthLargest(i....

题目

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

请实现 KthLargest 类：

KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。

int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

代码

class KthLargest { private int limit; private PriorityQueue<Integer> queue; public KthLargest(int k, int[] nums) { limit = k; queue = new PriorityQueue<>(k); for (int num : nums) { add(num); } } public int add(int val) { if (queue.size() < limit) { queue.add(val); } else if (val > queue.peek()) { queue.poll(); queue.add(val); } return queue.peek(); }}

总结

* 这是LeetCode上面的一道简单题目，主要考察优先队列的使用。

* Java封装了PriorityQueue，熟悉Java的API之后，就可以用来解决这个题目。

* 这个题目使用了小根堆来解决，题目要求是返回第k大元素，正好适合小根堆的性质。