703. Kth Largest Element in a Stream

Leetcode link

解题思路

本题要求我们给出流的第 k 大数字。

本题的核心思路在于，我们维护一个大小为 k 的排序数组，始终让它保存着前 k 大的数字。

有了数组之后，当流再次来数据的时候，有两种可能：

• 来的数据比第 k 大的数字小，则直接丢弃，返回原来的第 k 大的数字
• 来的数据比第 k 大的数字，把原来第 k 大的数字丢弃，之后把新数据在插入数组相应位置保持排序

只要处理好这两种状态这题就结束了

C++

class KthLargest {
 private:
  int size = 0;
  // 用了一个优先队列来封装插入的操作
  priority_queue<int, vector<int>, greater<int>> pq;

 public:
  KthLargest(int k, vector<int>& nums) {
    size = k;
    for (int num : nums) {
      add(num);
    }
  }

  int add(int val) {
    // 始终保持队列只有 k 个数字
    if (pq.size() < size) {
      pq.push(val);
    } else {
      // 比原来的第 k 大还大，就把原来的丢弃了把新的插进来
      if (val > pq.top()) {
        pq.pop();
        pq.push(val);
      }
    }
    return pq.top();
  }
};

Javascript

/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
    this.size = k;
    this.stream = nums.sort((a,b)=>b-a).slice(0,k);
};

/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    if(this.stream.length === 0 || val > this.stream[0]) {
        this.stream.unshift(val);
    }else if(val <= this.stream[this.stream.length-1]) {
        this.stream.push(val);
    }else{
          // 这里可以优化成 logn
        for(let i=0;i<this.stream.length-1;i++) {
          if (this.stream[i] >= val && this.stream[i + 1] < val) {
                    this.stream.splice(i+1, 0, val);
          break;
            }
        }
    }
    this.stream = this.stream.slice(0,this.size);
    return this.stream[this.size-1]
};