题目
题目来源leetcode
leetcode地址：239. 滑动窗口最大值，难度：困难。
题目描述(摘自leetcode)：
给你一个整数数组 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 示例 2： 输入：nums = [1], k = 1 输出：[1] 示例 3： 输入：nums = [1,-1], k = 1 输出：[1,-1] 示例 4： 输入：nums = [9,11], k = 2 输出：[11] 示例 5： 输入：nums = [4,-2], k = 2 输出：[4] 提示： 1 <= nums.length <= 105 -104 <= nums[i] <= 104 1 <= k <= nums.length
本地调试代码：
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { ... } public static void main(String[] args) { System.out.println(Arrays.toString(new Solution().maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3))); } }
题解
NO1：自定义队列
思路： 自定义一种队列规则，将入队元素依次从队列后往前比对，若是有小于的直接出队直到碰到大于的时候停止，接着再入队，此时队列队头一直会是最大值。
示例：1,3,-1,-3,5,3,6,7 k=3 队列 deque=[],左边是队头 下面=>指的是拿到队头的元素值，并没有直接出队 ① [1,3,-1],-3,5,3,6,7 首先先将第一组的元素入队，最终队列为[3] => 3 ② 1,[3,-1,-3],5,3,6,7 将1出队(队头若是1就将1出队，实际无)，接着入队-3，-3与队列从后往前比，最终队列为[3,-3] => 3 ③ 1,3,[-1,-3,5],3,6,7 将3出队(队头若是3就将3出队。实际有)，接着入队5，5与队列往后往前比，最终队列为[5] => 5 ④ 1,3,-1,[-3,5,3],6,7 将-1出队(队头若是-1就将-1出队。实际无)，接着入队3，3与队列往后往前比，最终队列为[5，3] => 5 ⑤ 1,3,-1,-3,[5,3,6],7 将6出队(队头若是-3就将-3出队。实际无)，接着入队6，6与队列往后往前比，最终队列为[6] => 6 ⑥ 1,3,-1,-3,5,[3,6,7] 将5出队(队头若是5就将5出队。实际无)，接着入队7，7与队列往后往前比，最终队列为[7] => 7 最终每组值为[3,3,5,5,6,7]
代码：
class MyQueue{ private Deque<Integer> deque; public MyQueue(){ deque = new LinkedList<>(); } //添加元素时，将队列从后往前比num小的出列 public void add(int num){ while(!deque.isEmpty() && deque.getLast() < num){ deque.pollLast(); } deque.addLast(num); } //队头元素若是与num相同则出队 public void pop(int num){ if(!deque.isEmpty() && num == deque.getFirst()){ deque.pollFirst(); } } //获取队头元素(最大的值) public int peek(){ return deque.getFirst(); } } class Solution { public int[] maxSlidingWindow(int[] nums, int k) { MyQueue myQueue = new MyQueue(); int[] maxNums = new int[nums.length-k+1]; //先将第一组的值放入，并且获取最大的值 for (int i = 0; i < k; i++) { myQueue.add(nums[i]); } maxNums[0] = myQueue.peek(); for (int i = 1; i < maxNums.length; i++) { //进来先去除不在范围内的元素 myQueue.pop(nums[i-1]); //添加新的元素 myQueue.add(nums[i+k-1]); //获取出当前队列中最大的元素 maxNums[i] = myQueue.peek(); } return maxNums; } }
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LqPo2Auu-1636733226055)(C:\Users\93997\AppData\Roaming\Typora\typora-user-images\image-20211103200737819.png)]
NO2：窗口内比较取值
思路：不使用某种数据结构，使用max、pos来临时存储最大值，max为最大值，pos为最大值索引。首先进行一轮比较得出对应的最大值，接着通过判断pos是否在下一次滑动窗口范围来进行相应的比较操作。
这里有一点不太清楚的是仅仅通过滑动窗口最左、最优右临界值来与最大值进行比较就能够让时间效率优化那么多？若是k为很大情况，那么临界最左-最右中间这些还是要一个一个进行比较，难道没有消耗特别多时间吗？(该题解与我最初思路一致，只不过没有想到的是多增加了下面第15行临界最左值判断就能优化时间效率那么多)
代码：
public int[] maxSlidingWindow(int[] nums, int k) { int[] maxNums = new int[nums.length - k + 1]; int pos = -1; int max = Integer.MIN_VALUE; for (int i = 0,winEndPos = k-1; i < maxNums.length; i++,winEndPos++) { if(pos >= i){ if(nums[winEndPos] >= max){ max = nums[winEndPos]; pos = winEndPos; } //下面nums[winEndPos]、nums[i]相当于窗口的最右侧与最左侧 }else if(nums[winEndPos] >= max-1){ //相当于>max，这里>=max-1，实际上是为了处理max = Integer.MIN_VALUE情况，-1由于超过原始长度就为最大值 max = nums[winEndPos]; pos = winEndPos; }else if(nums[i] >= max-1){ max = nums[i]; pos = i; }else{ //若是上面两个情况不过，那么就需要进行遍历重新比出最大值 max = nums[i]; for (int j = i+1; j < i + k; j++) { if (nums[j] > max) { max = nums[j]; pos = j; } } } maxNums[i] = max; } return maxNums; }
