[路飞]_leetcode-703-数据流中的第K大元素

输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]
解释：
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
复制代码

/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
    this.k = k;
    this.nums = nums;
    this.nums.sort((a,b) => b-a)
};
/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    this.nums.push(val);
    this.nums.sort((a,b)=> b-a)
    return this.nums[this.k-1]
};
复制代码

/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
    this.k = k;
    this.nums = nums;
    this.handle();
};
KthLargest.prototype.handle = function(){
    this.nums.sort((a,b)=> b-a)
    // 维护数组长度
    while(this.nums.length>this.k) this.nums.pop();
}
/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    this.nums.push(val);
    this.handle();
    return this.nums[this.k-1]
};
复制代码

/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
    this.k = k;
    this.nums = nums;
    this.handle();
};
KthLargest.prototype.handle = function(val){
// 当数组长度有K个元素且新插入的值小于第K个元素，不进行处理
    if(val!==undefined&&this.nums.length>=this.k&&val<this.nums[this.k-1]) return;
    this.nums.push(val);
    this.nums.sort((a,b)=> b-a)
    // 维护数组长度
    while(this.nums.length>this.k) this.nums.pop();
}
/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    this.handle(val);
    return this.nums[this.k-1]
};
复制代码

/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
    this.k = k;
    this.nums = nums;
    this.nums.sort((a,b)=> b-a)
};
KthLargest.prototype.handle = function(val){
    // 当数组长度有K个元素且新插入的值小于第K个元素，不进行处理
    if(val!==undefined&&this.nums.length>=this.k&&val<this.nums[this.k-1]) return;
    // 特判数组长度为1的情况
    if(this.nums.length === 1){
        if(this.nums[0]>val) this.nums.push(val)
        else this.nums.unshift(val)
    }else{
        // 二分查找合适的插入位置
        let l = 0,r = this.nums.length-1;
        while(l<r){
            const mid = (l+r) >> 1;
            if(this.nums[mid]>val) l = mid+1;
            else r = mid;
        }
        this.nums.splice(l,0,val)
    }
    // 维护数组长度
    while(this.nums.length>this.k) this.nums.pop();
}
/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    this.handle(val);
    return this.nums[this.k-1]
};
复制代码

/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
    this.heap = new MinHeap(k);
    for(let i = 0;i<nums.length;i++){
        this.heap.push(nums[i])
    }
};
/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    this.heap.push(val);
    return this.heap.top();
};
class MinHeap {
    constructor(max){
        this.arr = [];
        this.size = 0;
        this.max = max;
    }
    // 插入
    push(val){
        if(this.size>=this.max&&val<this.top()) return;
        this.arr.push(val);
        this.size++;
        // 插入操作后向上调整
        if(this.size>1){
            let cur =this.size-1;
            let parent = (cur-1) >> 1;
            while(cur>0&&this.arr[parent]>this.arr[cur]){
                [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]]
                cur = parent;
                parent = (cur-1) >> 1;
            }
        }
        // 维护最大个数
        while(this.size>this.max) this.pop();
    }
    // 弹出
    pop(){
        if(this.empty()) return;
        this.arr[0] = this.arr.pop();
        this.size--;
        // 弹出操作后向下调整
        let cur = 0,
        childl = cur*2+1,
        childr = cur*2+2;
        while(
            (childl<this.size&&this.arr[childl]<this.arr[cur])||
            (childr<this.size&&this.arr[childr]<this.arr[cur])
        ){
            if(childr<this.size&&this.arr[childr]<this.arr[childl]){
                [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]]
                cur = childr;
            }else{
                [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]]
                cur = childl;
            }
            childl = cur*2+1;
            childr = cur*2+2;
        }
    }
    // 获取堆顶元素
    top(){
        return this.arr[0]
    }
    // 判空
    empty(){
        return this.size === 0
    }
}
复制代码