原题
给定一个数组 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 <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
解法
思想
使用一个双端队列维护一个单调递减队列（但实际上存放的是数组的下标），每滑动一次窗口，如果进来的元素比队尾下标对应的元素小，则进入队尾，否则将队列尾比该元素小的元素都弹出（类似单调栈的思想），再进入队尾，那么任意时刻队首元素即为当前最大元素的下标，而如果滑动窗口后队首元素的下标等于当前下标-k，说明队首元素过期，应该从队列首部弹出。
代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> qmax = new LinkedList<>();
int[] ans = new int[nums.length-k+1];
int index = 0;
for(int i = 0;i<nums.length;i++){
while(!qmax.isEmpty()&&nums[qmax.peekLast()]<=nums[i]){
qmax.pollLast();
}
qmax.addLast(i);
if(qmax.peekFirst()==i-k){
qmax.pollFirst();
}
if(i>=k-1){
ans[index++] = nums[qmax.peekFirst()];
}
}
return ans;
}
}
下面这种方法的思想是记录当前窗口内最大元素的下标，如果滑出去了重新选举最大值，如果没滑出去将进来的元素与当前最大元素比较。它和暴力又不太一样，因为其实重新选举的次数较少，实际leetcode中这种方法反而更快，可能是因为数据量的原因：
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];
int maxIdx = 0;
//求出前k个元素的最大值索引
for(int i = 1; i < k; i++){
if(nums[i] > nums[maxIdx])maxIdx = i;
}
//li是滑动窗口的最左端
for(int li = 0; li < maxes.length; li++){
//ri是滑动窗口的最右端的索引
int ri = li + k- 1;
if(maxIdx < li){//最大值的索引不在滑动窗口范围内
maxIdx = li;
//求出[li, ri]范围内最大值的索引
for(int i = li + 1; i <= ri; i++){
if(nums[i] > nums[maxIdx])maxIdx = i;
}
}else if(nums[ri] >= nums[maxIdx]){//最大值的索引在滑动窗口的范围内，并且大于最大值
maxIdx = ri;
}
maxes[li] = nums[maxIdx];
}
return maxes;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode239-%e6%bb%91%e5%8a%a8%e7%aa%97%e5%8f%a3%e6%9c%80%e5%a4%a7%e5%80%bc/
