经典算法 —滑动窗口最大值
2019-03-22 本文已影响0人
刘彪lastbee
经典算法 —滑动窗口最大值
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[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
- 看到这个问题第一眼的想法是先遍历截取k为一个数据,找到最大的值
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
var result = []
for(var i = 0; i < nums-k; i++) {
var maxNum = nums[i]
for( var j = i + 1 ; j < i + k ; j++) {
if(nums[j] - nums[i]) {
maxNum = nums[j]
}
}
result.push(maxNum )
}
return result
};
- 换个思路就是一个队列问题,一次性放入数据,最前面的永远是最大的,最后一个,比前面的大的话,前面的数据都可以清除
/**
* @author lastbee@163.com
* @param {number []} nums
* @param {number} k
* @return {number []}
*/
var slidingWindow = function(nums, k) {
if (nums.length == 0) return []
let window = []//队列用来存放下标
let result= []
for((val i= 0;i < nums.length-1 ; i ++) {
if( i >= k && window[0] <= index- k ) {
window.shift()//队列头抛出
}
for(var j = window.length-1; j>= 0; j--) {
if(nums[window[window.length - 1]] <= nums[i]) {
window.pop()
} else {
break;
}
}
v window.push(index)
if (index >= k - 1) {
result.push(nums[window[0]])
}
}
return result
}
- 优化之后
/**
* @author lastbee@163.com
* @param {number []} nums
* @param {number} k
* @return {number []}
*/
var slidingWindow = function(nums, k) {
if (nums.length == 0) return []
let window = []//队列用来存放下标
let res = []
nums.forEach((item, index) => {
if (index >= k && window[0] <= index - k) {
window.shift()//队列头抛出
}
while (window && nums[window[window.length - 1]] <= item) {
window.pop()//队列为抛出
}
window.push(index)
if (index >= k - 1) {
res.push(nums[window[0]])
}
})
return res
}