Files
2021-02-11 21:12:13 +08:00

93 lines
2.6 KiB
Markdown
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

# [703. Kth Largest Element in a Stream](https://leetcode.com/problems/kth-largest-element-in-a-stream/)
## 题目
Design a class to find the `kth` largest element in a stream. Note that it is the `kth` largest element in the sorted order, not the `kth` distinct element.
Implement `KthLargest` class:
- `KthLargest(int k, int[] nums)` Initializes the object with the integer `k` and the stream of integers `nums`.
- `int add(int val)` Returns the element representing the `kth` largest element in the stream.
**Example 1:**
```
Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]
Explanation
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
```
**Constraints:**
- `1 <= k <= 104`
- `0 <= nums.length <= 104`
- `104 <= nums[i] <= 104`
- `104 <= val <= 104`
- At most `104` calls will be made to `add`.
- It is guaranteed that there will be at least `k` elements in the array when you search for the `kth` element.
## 题目大意
设计一个找到数据流中第 k 大元素的类class。注意是排序后的第 k 大元素,不是第 k 个不同的元素。请实现 KthLargest 
- KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
- int add(int val) 将 val 插入数据流 nums 后,返回当前数据流中第 k 大的元素。
## 解题思路
- 读完题就能明白这一题考察的是最小堆。构建一个长度为 K 的最小堆,每次 pop 堆首(堆中最小的元素),维护堆首即为第 K 大元素。
- 这里有一个简洁的写法,常规的构建一个 pq 优先队列需要自己新建一个类型,然后实现 Len()、Less()、Swap()、Push()、Pop() 这 5 个方法。在 sort 包里有一个现成的最小堆sort.IntSlice。可以借用它再自己实现 Push()、Pop()就可以使用最小堆了,节约一部分代码。
## 代码
```go
package leetcode
import (
"container/heap"
"sort"
)
type KthLargest struct {
sort.IntSlice
k int
}
func Constructor(k int, nums []int) KthLargest {
kl := KthLargest{k: k}
for _, val := range nums {
kl.Add(val)
}
return kl
}
func (kl *KthLargest) Push(v interface{}) {
kl.IntSlice = append(kl.IntSlice, v.(int))
}
func (kl *KthLargest) Pop() interface{} {
a := kl.IntSlice
v := a[len(a)-1]
kl.IntSlice = a[:len(a)-1]
return v
}
func (kl *KthLargest) Add(val int) int {
heap.Push(kl, val)
if kl.Len() > kl.k {
heap.Pop(kl)
}
return kl.IntSlice[0]
}
```