- Sliding Window Maximum
You are given an array of integers nums
, there is a sliding window of size k
which is moving from the very left of the array to the very right. You can only see the k
numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
**Input:** nums = [1,3,-1,-3,5,3,6,7], k = 3
**Output:** [3,3,5,5,6,7]
**Explanation:**
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 **3**
1 [3 -1 -3] 5 3 6 7 **3**
1 3 [-1 -3 5] 3 6 7 ** 5**
1 3 -1 [-3 5 3] 6 7 **5**
1 3 -1 -3 [5 3 6] 7 **6**
1 3 -1 -3 5 [3 6 7] **7**
Example 2:
**Input:** nums = [1], k = 1
**Output:** [1]
Constraints:
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
Idea
* 使用最大堆
* 使用双端队列(*)
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
let window = [] // 存放数组元素在窗口内的索引
let result = []
for( let i=0; i < nums.length; i++){
// 向右移动窗口
if( i>=k && window[0] <= i-k ){
window.shift();
}
// 将队尾窗口比当前值小的索引删除掉
while( window.length > 0 && nums[window[window.length-1]] < nums[i] ){
window.pop();
}
// 将当前所以加入
window.push(i)
// 收集当前窗口最大值
if(i >= k-1 ){
result.push(nums[window[0]]);
}
}
return result
};