mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-01-10 18:48:13 +08:00
58 lines
2.8 KiB
HTML
58 lines
2.8 KiB
HTML
<p>You are part of a university admissions office and need to keep track of the <code>kth</code> highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.</p>
|
|
|
|
<p>You are tasked to implement a class which, for a given integer <code>k</code>, maintains a stream of test scores and continuously returns the <code>k</code>th highest test score <strong>after</strong> a new score has been submitted. More specifically, we are looking for the <code>k</code>th highest score in the sorted list of all scores.</p>
|
|
|
|
<p>Implement the <code>KthLargest</code> class:</p>
|
|
|
|
<ul>
|
|
<li><code>KthLargest(int k, int[] nums)</code> Initializes the object with the integer <code>k</code> and the stream of test scores <code>nums</code>.</li>
|
|
<li><code>int add(int val)</code> Adds a new test score <code>val</code> to the stream and returns the element representing the <code>k<sup>th</sup></code> largest element in the pool of test scores so far.</li>
|
|
</ul>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong><br />
|
|
<span class="example-io">["KthLargest", "add", "add", "add", "add", "add"]<br />
|
|
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">[null, 4, 5, 5, 8, 8]</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);<br />
|
|
kthLargest.add(3); // return 4<br />
|
|
kthLargest.add(5); // return 5<br />
|
|
kthLargest.add(10); // return 5<br />
|
|
kthLargest.add(9); // return 8<br />
|
|
kthLargest.add(4); // return 8</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong><br />
|
|
<span class="example-io">["KthLargest", "add", "add", "add", "add"]<br />
|
|
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">[null, 7, 7, 7, 8]</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);<br />
|
|
kthLargest.add(2); // return 7<br />
|
|
kthLargest.add(10); // return 7<br />
|
|
kthLargest.add(9); // return 7<br />
|
|
kthLargest.add(9); // return 8</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>0 <= nums.length <= 10<sup>4</sup></code></li>
|
|
<li><code>1 <= k <= nums.length + 1</code></li>
|
|
<li><code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code></li>
|
|
<li><code>-10<sup>4</sup> <= val <= 10<sup>4</sup></code></li>
|
|
<li>At most <code>10<sup>4</sup></code> calls will be made to <code>add</code>.</li>
|
|
</ul>
|