Leetcode Heap
703 数据流中的第K大元素
// 30.43% 好像是5% orz /** * @param {number} k * @param {number[]} nums */ var KthLargest = function(k, nums) { this.sortedNums = nums.sort((a, b) => b - a); this.kmax = this.sortedNums[k-1] this.k = k }; /** * @param {number} val * @return {number} */ KthLargest.prototype.add = function(val) { if (!this.kmax) { this.sortedNums.push(val) this.sortedNums.sort((a, b) => b - a) this.kmax = this.sortedNums[this.k-1]; return this.kmax } if (val <= this.kmax) return this.kmax let tmp = [], flag = true let i = 0, j = 0; // console.log(this.k, this.sortedNums[j]) while (i < this.k){ if (val > this.sortedNums[j] && flag){ tmp[i++] = val flag = false }else{ tmp[i++] = this.sortedNums[j++] } } this.sortedNums = tmp this.kmax = this.sortedNums[this.k-1] return this.kmax }; /** * Your KthLargest object will be instantiated and called as such: * var obj = new KthLargest(k, nums) * var param_1 = obj.add(val) */
因为只要第k大的元素，所以，只要保存k个最大的元素，每次返回最小的那个就可以了。每次add操作先跟最小的元素判断，如果比最小的还小，就直接返回当前最小的这个数即可。否则重新调整这k个元素。因此要做的是维护一个最小值，并且动态调整。可以用最小堆来做，最小的永远都是堆顶元素，如果新add的元素小于堆顶，直接返回堆顶元素。否则将堆顶元素直接替换成新元素，再从上到下进行调整。而初始化堆的时候，则从下往上调整保证堆顶的最小。
// 144ms 95.08% 44.7mb 44.12% var KthLargest = function(k, nums) { this.k = k this.knums = [] this.swap = function(arr, i, j){ let tmp = arr[i] arr[i] = arr[j] arr[j] = tmp } for (let i of nums){ this.add(i) } }; KthLargest.prototype.add = function(val) { let len = this.knums.length; if (len === 0){ this.knums[1] = val return this.knums[1] } if (len-1 < this.k){ // 因为第0个元素不用，从第一个元素开始存 let cur = len this.knums[cur] = val let parent = cur%2 === 0 ? cur/2 : (cur-1)/2 while(this.knums[parent] > this.knums[cur]){ this.swap(this.knums, parent, cur) cur = parent parent = cur%2 === 0 ? cur/2 : (cur-1)/2 } }else{ if (this.knums[1] >= val){ return this.knums[1] } this.knums[1] = val let cur = 1 while(this.knums[cur*2] !== undefined){ let min = cur*2 if (this.knums[cur*2 + 1] !== undefined && this.knums[cur*2] > this.knums[cur*2 + 1]){ min = cur*2+1 } if (this.knums[cur] > this.knums[min]){ this.swap(this.knums, min, cur) cur = min }else{ break } } } return this.knums[1] }; // let k = 3; // let arr = [4,5,8,2]; // let kthLargest = new KthLargest(k, arr); // console.log(kthLargest.add(3)); // returns 4 // console.log(kthLargest.add(5)); // returns 5 // console.log(kthLargest.add(10)); // returns 5 // console.log(kthLargest.add(9)); // returns 8 // console.log(kthLargest.add(4)); // returns 8 // let k = 1; // let arr = []; // let kthLargest = new KthLargest(k, arr); // console.log(kthLargest.add(-3)); // returns -3 // console.log(kthLargest.add(-2)); // returns -2 // console.log(kthLargest.add(-4)); // returns -2 // console.log(kthLargest.add(0)); // returns 0 // console.log(kthLargest.add(4)); // returns 4 // let k = 2; // let arr = [0]; // let kthLargest = new KthLargest(k, arr); // console.log(kthLargest.add(-1)); // returns -1 // console.log(kthLargest.add(1)); // returns 0 // console.log(kthLargest.add(-2)); // returns 0 // console.log(kthLargest.add(-4)); // returns 0 // console.log(kthLargest.add(3)); // returns 1
239 滑动窗口最大值
// 96ms 97.64% 41.1MB 88.14% /** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSlidingWindow = function(nums, k) { if (!nums) return [] let window = [], res = [] for (let i = 0; i < nums.length; i++){ if (window[0] !== undefined && i >= k + window[0]){ window.shift() } while(window.length > 0 && nums[window[window.length-1]] <= nums[i]){ window.pop() } window.push(i) if (window[0] !== undefined && i >= k-1){ res.push(nums[window[0]]) } } return res }; // console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3)) // [ 3, 3, 5, 5, 6, 7 ] // console.log(maxSlidingWindow([7, 2, 4], 2)) // [ 7, 4 ]
window用来保存在当前窗口中的元素索引，res保存每次移动的最大值结果。while循环保证当前窗口中的最左边也就是第一个元素一定是最大值元素，第一个if：当元素移出窗口时，直接移除掉该元素。性能惊人。