网站如何进行建设,全域seo,怎么给网站做友情链接,wordpress aliay滑动窗口的最大值
题目描述#xff1a;
给定一个长度为 n 的数组 num 和滑动窗口的大小 size #xff0c;找出所有滑动窗口里数值的最大值。
例如#xff0c;如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3#xff0c;那么一共存在6个滑动窗口#xff0c;他们的最大值…滑动窗口的最大值
题目描述
给定一个长度为 n 的数组 num 和滑动窗口的大小 size 找出所有滑动窗口里数值的最大值。
例如如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3那么一共存在6个滑动窗口他们的最大值分别为{4,4,6,6,6,5} 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个 {[2,3,4],2,6,2,5,1} {2,[3,4,2],6,2,5,1} {2,3,[4,2,6],2,5,1} {2,3,4,[2,6,2],5,1} {2,3,4,2,[6,2,5],1} {2,3,4,2,6,[2,5,1]}。
窗口大于数组长度或窗口长度为0的时候返回空。 数据范围 1≤n≤100000≤size≤10000数组中每个元素的值满足 ∣val∣≤10000 要求空间复杂度 O(n)时间复杂度 O(n) 示例1 输入[2,3,4,2,6,2,5,1],3 返回值[4,4,6,6,6,5] 示例2 输入[9,10,9,-7,-3,8,2,-6],5 返回值[10,10,9,8] 示例3 输入[1,2,3,4],5 返回值[]
解题思路
方法一双端队列Deque
初始化一个空的双端队列和一个空的结果数组。遍历数组中的每个元素对于每个元素 移除双端队列中不在滑动窗口范围内的元素的索引。移除双端队列中小于当前元素的元素的索引因为它们不可能是最大值。将当前元素的索引添加到双端队列中。当滑动窗口完全在数组内时将双端队列首部的元素添加到结果数组中。 返回结果数组。
方法一JavaScript版本代码如下
function maxSlidingWindow(nums, size) {if (size 0 || size nums.length) return [];const result [];const deque []; // 双端队列用于存储索引for (let i 0; i nums.length; i) {// 移除不在滑动窗口内的元素的索引while (deque.length deque[0] i - size 1) {deque.shift();}// 移除比当前元素小的元素的索引因为它们不可能是最大值while (deque.length nums[deque[deque.length - 1]] nums[i]) {deque.pop();}// 将当前元素的索引添加到双端队列中deque.push(i);// 当滑动窗口完全在数组内时将当前窗口的最大值添加到结果中if (i size - 1) {result.push(nums[deque[0]]);}}return result;
}// 示例
console.log(maxSlidingWindow([2, 3, 4, 2, 6, 2, 5, 1], 3)); // [4, 4, 6, 6, 6, 5]
console.log(maxSlidingWindow([9, 10, 9, -7, -3, 8, 2, -6], 5)); // [10, 10, 9, 8]
console.log(maxSlidingWindow([1, 2, 3, 4], 5)); // []方法二单调递减栈
初始化一个空的单调递减栈和一个空的结果数组。遍历数组中的每个元素对于每个元素 弹出栈顶元素直到栈为空或者栈顶元素小于当前元素。如果弹出的元素索引对应的窗口已经超出范围则忽略。如果栈为空或者栈顶元素对应的窗口正好是当前窗口则将栈顶元素对应的最大值添加到结果数组中。将当前元素的索引压入栈中。 返回结果数组。
方法二JavaScript版本代码
function maxSlidingWindow(nums, size) {if (size 0 || size nums.length) return [];const result [];const stack []; // 单调递减栈用于存储索引for (let i 0; i nums.length; i) {// 弹出栈顶元素直到栈为空或者栈顶元素对应的值小于当前元素while (stack.length nums[stack[stack.length - 1]] nums[i]) {const index stack.pop();// 如果弹出的索引对应的窗口已经不在范围内则跳过if (i - index 1 size) {continue;}// 如果栈为空或者栈顶元素对应的窗口在范围内则将当前最大值加入结果if (stack.length 0 || i - stack[stack.length - 1] 1 size) {result.push(nums[index]);}}// 将当前元素的索引压入栈中stack.push(i);}return result;
}// 示例
console.log(maxSlidingWindow([2, 3, 4, 2, 6, 2, 5, 1], 3)); // [4, 4, 6, 6, 6, 5]
console.log(maxSlidingWindow([9, 10, 9, -7, -3, 8, 2, -6], 5)); // [10, 10, 9, 8]
console.log(maxSlidingWindow([1, 2, 3, 4], 5)); // []总结与类似题解题思路
解决滑动窗口最大值问题的关键在于维护一个能够快速访问当前窗口最大值的机制。这可以通过以下步骤实现
使用双端队列或单调栈来维护一个有序的序列使得我们可以快速访问最大值。在遍历数组的过程中不断调整这个有序序列确保它始终反映当前窗口的最大值。当窗口滑动时及时移除不再属于窗口的元素并添加新进入窗口的元素。在窗口完全在数组内时记录窗口的最大值。
对于类似的滑动窗口问题如求最小值、求平均值等都可以采用类似的思路关键在于如何维护一个能够快速提供所需信息的辅助数据结构。这种方法的时间复杂度通常是O(n)因为我们每个元素最多只会被推入和弹出辅助数据结构一次。
