给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
示例 1：
输入：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
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
思路一：利用双端队列(单调队列)来实现，队列从大到小排列，每次给尾部添加时都跟队列中尾部的值对比，比要添加的小就删除；直到nums[队尾]>nums[i] 为止，接下来添加；然后更新滑动窗口左边索引，并存储最大值
时间复杂度： O(n)
空间复杂度： O(1)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//处理边界条件
if(nums==null||nums.length==0||k<1) return new int[0];
if(k==1) return nums;
int[] maxes = new int[nums.length - (k-1)];
/**
创建双端队列(单调队列)
使用：
peek:取值(偷偷瞄一眼) 等价于 get
poll:删除(削) 等价于 remove
offer:添加(入队) 等价于 add
*/
Deque<Integer> deque = new ArrayDeque<>();
for(int ri = 0; ri < nums.length;ri++) {
//1.如果nums[i] >= nums[队尾]，就不断删除队尾 直到nums[队尾]>nums[i] 为止
while(!deque.isEmpty() && nums[ri] >= nums[deque.peekLast()]){
deque.pollLast();
}
//2.将i索引加入队尾
deque.offerLast(ri);
//3. 如果wi>=0 先验证有效性
int wi = ri - k + 1; //wi就是滑动窗口最左索引
if(wi<0) continue;
/**
1>如果队头失效，就移除队头(队头 < wi 就代表失效,因为队头在w索引的左边 不在滑动窗口范围内)
2>未失效，设置w窗口的最大值为nums[队头]
*/
if(deque.peekFirst() < wi) deque.pollFirst();
maxes[wi] = nums[deque.peekFirst()];
}
return maxes;
}
}
执行结果.png
思路二： 暴力法，先求出第一个滑动窗口的最大值；设左右边界，向右移动 每进来一个新值就跟最大值对比，更新当前滑动窗口的最大值；
注意：此方法在我2022年7月 实验的时候已经不适用了，应该是官方新增了测试用例，导致性能很低 跑完所有用例时间需要1000ms，属于垫底的存在
//暴力法
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//处理边界条件
if(nums==null||nums.length==0||k<1) return new int[0];
if(k==1) return nums;
int[] maxes = new int[nums.length - (k-1)];
//1.先求出第一段k各元素的最大值
int maxIdx = 0;
for(int i = 1; i < k; i++){
if(nums[i] >= nums[maxIdx]) maxIdx = I;
}
//2.li、ri 滑动左右边界，对比求出最大值；得到结果后添加到数组
for(int li = 0; li < maxes.length;li++) {
int ri = li + k - 1;
//最大值索引不在滑动窗口范围内
if(maxIdx < li) {
//求最大值，先假设li位置的是最大值
maxIdx = li;
for(int i = li+1 ;i <= ri;i++) {
if(nums[i] >= nums[maxIdx]) maxIdx = I;
}
}else if(nums[ri] >= nums[maxIdx]) {//在滑动窗口范围内 && 大于等于新进来的值
maxIdx = ri;
}
//li:表示滑动窗口的索引
maxes[li] = nums[maxIdx];
}
return maxes;
}
}
