网购电商平台_优秀营销策划方案_口碑营销的好处_企业培训心得

1、题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

2、解答思路

本题需要遍历每个滑动窗口，然后求出滑动窗口的最大值，重点在于如何将求出滑动窗口最大值的时间复杂度降到O(1)。因此可以使用单调的双端队列。假设循环遍历将nums[i]添加到队列中，每次将i++，那么滑动窗口往后移一位。

• 在讨论下一个滑动窗口之前，判断当前窗口的最大值是否是对应数组的第一个元素，若是，即当前窗口的元素个数为k，则移除第一个元素，以便后续元素加入。
• 若nums[i]大于队列中的末尾元素，则移除队列中所有小于nums[i]的元素，确保队列的单调属性，相当于比较得出较大的元素。
• 若nums[i]小于队列中的末尾元素，则直接添加到队列末尾，不移除的原因是其可能成为后面滑动窗口的最大值。

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {// 定义结果数组int[] ans = new int[nums.length-k+1];// 结果数组的下标int index = 0;// 定义单调双端队列Deque<Integer> deque = new LinkedList<>();// 未形成窗口之前for(int i=0;i<k;i++){// 移除队列中所有小于num[i])的元素，确保队列单调递减while(!deque.isEmpty() && deque.peekLast()<nums[i])deque.removeLast();deque.addLast(nums[i]);}// 获取第一个窗口的最大值ans[index++] = deque.peekFirst();// 形成窗口之后for(int i=k;i<nums.length;i++){// 如果之前窗口的最大值为对于数组的第一个元素，即滑动窗口满了，则移除第一个元素if(deque.peekFirst() == nums[i-k])deque.removeFirst();// 移除队列中所有小于num[i])的元素，确保队列单调递减while(!deque.isEmpty() && deque.peekLast()<nums[i])deque.removeLast();deque.addLast(nums[i]);ans[index++] = deque.peekFirst();}return ans;}
}

• 时间复杂度 O(n) ： 其中 n 为数组 nums 长度。线性遍历 nums 占用 O(n) ；每个元素最多仅入队和出队一次，因此单调队列 deque 占用 O(2n) ，因此总的来说是O(n)。
• 空间复杂度 O(k) ： 双端队列 deque 中最多同时存储 k 个元素。