Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-05-23 23:29:54
https://leetcode.com/problems/kth-largest-element-in-a-stream/description/
703. Kth Largest Element in a Stream
設計一個資料流,他提供一個增加元素到流的方法並返回第k大的元素。
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
思路:
1.維護一個大小為k的MinHeap,如果size不為k的時候直接入隊,如果size等於k的話
就比較Heap最小的元素,如果新加入的元素更大就把最小元素Pop出來。
2.每次都返回Heap頂端的元素。
Java Code:

Links booklink

Contact Us: admin [ a t ] ucptt.com