输入：整数数组nums，滑动窗口大小k 输出：整数数组 规则：在一个窗口内只能看到k个数，找一个最大的数，添加到返回数组中。每次滑动向右滑动一步。
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max
[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
只能想到暴力的思路。每次窗口范围内比较k个元素大小。所以时间复杂度是O(nk)。
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums==null || nums.length==0) return null; if(k==0) return nums; int n = nums.length; int[] r = new int[n-k+1]; for(int i=0;i<n-k+1;i++){ r[i] = nums[i]; for(int j=i;j<i+k;j++){ r[i] = Math.max(r[i],nums[j]); } } return r; } }看了力扣官方解释想起来了，当时做的时候确实蒙圈。
队列是一个双端队列。队列中存放的是当前窗口内的k个元素的下标。注意这里不存元素，存下标。队列头部的元素是窗口范围内，最大值元素的下标。例如：nums=[1,3,-1,-3,5,3,6,7] ,在{-1,-3,5}这个窗口范围内，队列头部存放的元素值是4。队列尾部存放的元素是当前窗口内最大值元素的下标。最大值是5，下标是4。 每次添加下标为i的元素的时候： 1 检查队列头部元素是不是等于i-k。是，就删除。 2 不断拿nums[i]与队尾元素比较。如果nums[i]>nums[队尾元素]，则删除队尾元素，在队尾插入i。否则不做任何操作。 队列中元素的nums值是不断递减的。
class Solution { private ArrayDeque<Integer> deq = new ArrayDeque<Integer>(); private int[] nums; private int k; public int[] maxSlidingWindow(int[] nums, int k) { if(nums==null || nums.length==0) return null; if(k==0) return nums; int n = nums.length; this.nums = nums; this.k = k; int[] r = new int[n-k+1]; deq = new ArrayDeque<Integer>(); for(int i=0;i<k;i++){ add(i); } r[0] = nums[deq.getFirst()]; for(int i=k;i<n;i++){ add(i); r[i-k+1] = nums[deq.getFirst()]; } return r; } private void add(int i){ if(!deq.isEmpty() && deq.getFirst()==i-k){ deq.removeFirst(); } while(!deq.isEmpty() && nums[deq.getLast()]<nums[i]){ deq.removeLast(); } deq.addLast(i); } }