代码拉取完成,页面将自动刷新
同步操作将从 老胡来也/EveryDay 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个整数数组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
输入:nums = [1], k = 1
输出:[1]
输入:nums = [1,-1], k = 1
输出:[1,-1]
输入:nums = [9,11], k = 2
输出:[11]
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
const indexGroup = [], maxGroup = [];
nums.forEach((v,i) => {
if(i >= k && indexGroup[0] <= i-k) indexGroup.shift();
while(indexGroup && nums[indexGroup[indexGroup.length-1]] <= v) indexGroup.pop();
indexGroup.push(i);
if(i >= k-1) maxGroup.push(nums[indexGroup[0]]);
})
return maxGroup;
};
// 普通做法超时 需要优化的实现方式
// var maxSlidingWindow = function(nums, k) {
// const maxGroup = [];
// for(let i=0,n=nums.length; i<=n-k; ++i){
// maxGroup.push(Math.max(...nums.slice(i, i+k)));
// }
// return maxGroup;
// };
是猛男就要爆破的方式不管用了,超时警告,那么只能优化做法,实际上对于两个相邻的滑动窗口,它们共用着k-1
个元素,而只有1
个元素是变化的,我们可以根据这个特点进行优化。我们可以通过维护一个单调递减的窗口来实现,当向右移动时左侧超出窗口的值弹出,因为需要的是窗口内的最大值,所以只要保证窗口内的值是递减的即可,即小于新加入的值全部弹出,最左端即为窗口最大值。首先我们定义一个用来存储递减值的下标的窗口,以及存储最大值的组,之后循环给定的数组,如果当前遍历的数组值下标大于窗口大小并且递减下标窗口的第一个值是小于当前窗口,即第一个值在当前需要组合的窗口之外,就将其弹出,之后从后向前遍历,如果递减窗口存在值且其中的值小于即将要加入的值就将其弹出,此时将当前遍历的值的下标加入递减窗口,最后如果窗口能够组合成k
个就开始取最大值即递减窗口的第一个值,将其加入最大值组,循环结束后返回即可。
https://github.com/WindrunnerMax/EveryDay
https://leetcode-cn.com/problems/sliding-window-maximum/
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。