239. 滑动窗口最大值

239. 滑动窗口最大值

给你一个整数数组 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 LinkedList<>();

       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. 如果w>=0 先验证有效性
           int li = ri - k + 1;
           if(li<0) continue;
        
          /**
           1>如果队头失效，就移除队头(队头 < w 就代表失效,因为队头在w索引的左边 不在滑动窗口范围内)
           2>未失效，设置w窗口的最大值为nums[队头]
           */
          if(deque.peekFirst() < li) deque.pollFirst();
          
          maxes[li] = nums[deque.peekFirst()];
          
       }

       return maxes;
    }
}

思路二： 暴力法，先求出第一个滑动窗口的最大值；设左右边界，向右移动 每进来一个新值就跟最大值对比，更新当前滑动窗口的最大值；

注意：此方法在我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;
    }
}