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：当元素移出窗口时，直接移除掉该元素。性能惊人。