case1:双指针+回溯 时间复杂度O(n^2),空间复杂度O(n)
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int len = nums.length; if(len==0||len<k) return new int[0]; int left = 0,right = 0; int max = nums[left]; int[] res = new int[len-k+1]; int idx = 0; while(right<len){ max = Math.max(max,nums[right]); if(right-left+1==k){//当窗口内的元素数量为k时 res[idx++] = max; left++; right = left; max = Integer.MIN_VALUE;//注意这里不能直接将max更新为nums[left]，因为此时有可能下标越界 }else{ right++; } } return res; } }case2:使用单调(递减)队列，维护这么一个单调队列，期内元素为数组的下标i的值(不能是nums[i]，是为了方便统计此时这个单调队列中元素的个数)，当其内元素的数量为k时，(左移窗口)，此时为了保证队列中元素的单调递减特性，移除比nums[i]小的元素的索引，然后再插入索引i,然后去判定此时窗口大小是否为k，是的话，则队头元素即为此时窗口中的最大值。（这里注意一下:当i>=k-1时，此时窗口大小刚好为k，此后每新插入一个索引，都会构成一个窗口大小刚好为k的窗口，因为之前窗口的大小刚好为k,然后为k时，我们移除左边的那个，此时窗口大小为k-1,再新增一个，窗口大小又恢复为k） 时间复杂度为O(n),空间复杂度为O(k)
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int len = nums.length; if(len==0||len<k) return new int[0]; LinkedList<Integer> dequeue = new LinkedList<>(); int[]res = new int[len-k+1];//这len-k+1个大小为k的窗口是分别以0,1...len-k为起点的窗口，共len-k+1个 int idx = 0; for(int i=0;i<len;i++){ if(!dequeue.isEmpty()&&i-dequeue.getFirst()+1>k){//维护窗口大小？ dequeue.poll(); } //添加新元素之前，先保证单调性 while(!dequeue.isEmpty()&&nums[dequeue.getLast()]<nums[i]){ dequeue.pollLast(); } dequeue.offer(i); //当窗口大小为k时，记录窗口内的最大值 if(i>=k-1){ res[idx++] = nums[dequeue.peekFirst()]; } } return res; } }