Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/05/23 23:29)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串328/719 (看更多)

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： ----------------------------------------------- class KthLargest { private final PriorityQueue<Integer> heap; private final int k; public KthLargest(int k, int[] nums) { this.heap = new PriorityQueue<>(); this.k = k; for (int num : nums) { add(num); } } public int add(int val) { if (heap.size() < k) { heap.add(val); } else if (heap.peek() < val) { heap.poll(); heap.add(val); } return heap.peek(); } } ----------------------------------------------- -- https://i.imgur.com/bFRiqA3.jpg