[JavaScript 刷题] 堆 - 数据流中的第 K 大元素, leetcode 703

github repo 地址: https://github.com/GoldenaArcher/js_leetcode，Github 的目录 大概 会更新的更勤快一些。

题目地址：703. Kth Largest Element in a Stream

题目

如下：

Design a class to find the k^th largest element in a stream. Note that it is the k^th largest element in the sorted order, not the k^th 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) Appends the integer val to the stream and returns the element representing the k^th largest element in the stream.

解题思路

整体来说没有什么特别难的地方，用 Min Heap 或者 BST 去解这道题都可以，不过因为是 leectode 上出现的这道题，最近又发现了一个 leetcode 中已经实现的 JavaScript 特有的 Heap 类，因此就在这里放一下了。

只在 leetcode 上刷题的，可以看一下这个类：MaxPriorityQueue 以及对应的 MinPriorityQueue，目前看到实现的功能有：

• constructor

  constructor 的用法如下：

  this.pq = new MaxPriorityQueue({ priority: (x) => -x });
  1

  其中的 priority 就是一个 comparator，这样的话保存一些特殊的结点也是可以实现的。

• enqueue

• dequeue

• front

• back

使用 JavaScript 解题

/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function (k, nums) {
  this.pq = new MaxPriorityQueue({ priority: (x) => -x });
  this.size = k;

  for (const num of nums) {
    this.pq.enqueue(num);

    if (this.pq.size() > this.size) {
      // console.log(this.pq.dequeue());
      this.pq.dequeue();
    }
  }
};

/**
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function (val) {
  this.pq.enqueue(val);
  if (this.pq.size() > this.size) {
    this.pq.dequeue();
    // console.log(this.pq.dequeue());
  }
  return this.pq.front().element;
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * var obj = new KthLargest(k, nums)
 * var param_1 = obj.add(val)
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36