滑动窗口内最大值最小值问题

滑动窗口是一种想象出来的数据结构：
滑动窗口有左边界L和右边界R，在数组或者字符串或者一个序列上，即为S，窗口就是S[L,R]这一部分，
L往右滑动意味着一个样本出了窗口，R往右滑动一位置一个样本进了窗口，L和R都只能向右侧滑动。

意义：
L++ 减小窗口， R++扩大窗口

双端队列的含义：
假设此时逐步缩小窗口大小，哪些位置的数会依次成为窗口内的最大值！

该窗口结构时间复杂度分析：
窗口不管是L和R滑动之后，都会让窗口呈现新的状况，如何能够更快的得到窗口当前状态下的最大值和最小值？通过双端队列实现，每个元素平均代价为O(1)!
分析如下：
L和R窗口位置会滑过数组中所有的数字，那么在双端队列中，每一个位置最多进一次双端队列，出一次双端队列。（进只能从队尾进，出去可能从队尾被动出，也可能从队头主动出（获取当前窗口状态下的最大值或者最小值））
窗口在运动的过程中，双端队列更新的总代价为O(N)，平均每个元素代价为O(1),
每次获取的最大值或者最小值就是双端队列的头部元素，直接通过queue.peekFirst()获取，O(1)。

双端队列中数据严格从大到小排列，当左侧窗口缩小时，比较是否队列头部元素是否过期（queue.peek()=L），过期出队列。

题目1：

给定一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位
返回 滑动窗口中的最大值 。
https://leetcode-cn.com/problems/sliding-window-maximum

固定窗口内的最大值，双端队列中存放的是原数组的下标。
13. 滑动窗口最大最小值更新结构 - 图1

  1. package class24;
  3. import java.util.LinkedList;
  5. /**
  6.  * 给定一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。
  7.  * 你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。
  8.  * 返回 滑动窗口中的最大值 。
  9.  *
  10.  * leetcode 239 https://leetcode-cn.com/problems/sliding-window-maximum
  11.  */
  12. public class Code01_SlidingWindowMaxArray {
  14.     // 方式1. 暴力的对数器方法
  15.     public static int[] right(int[] arr, int w) {
  16.         if (arr == null || w < 1 || arr.length < w) {
  17.             return null;
  18.         }
  19.         int N = arr.length;
  20.         int[] res = new int[N - w + 1];
  21.         int index = 0;
  22.         // 初始窗口
  23.         int L = 0;
  24.         int R = w - 1;
  25.         while (R < N) {
  26.             // 每次遍历的获取窗口内的最大值
  27.             int max = arr[L];
  28.             for (int i = L + 1; i <= R; i++) {
  29.                 max = Math.max(max, arr[i]);
  30.             }
  31.             res[index++] = max;
  32.             L++;
  33.             R++;
  34.         }
  35.         return res;
  36.     }
  38.     // 方式2. 双端队列实现窗口内最大值结构  w为窗口固定大小
  39.     /**
  40.      * 窗口最大值结构
  41.      * 获取固定窗口内最大值，返回每次窗口的最大值组成的数组
  42.      *
  43.      * @param arr
  44.      * @param w   固定窗口大小
  45.      * @return
  46.      */
  47.     public static int[] getMaxWindow(int[] arr, int w) {
  48.         if (arr == null || w < 1 || arr.length < w) {
  49.             return null;
  50.         }
  51.         // qmax 窗口最大值的更新结构
  52.         // gmax 双端队列内放下标，而不是放值，通过arr查出值
  53.         LinkedList<Integer> qmax = new LinkedList<>(); // 头部大尾部小
  55.         int[] res = new int[arr.length - w + 1];
  56.         int index = 0;// res数组下标位置
  58.         // R表示窗口的右边界，R表示数组下标。
  59.         for (int R = 0; R < arr.length; R++) { // 窗口右边界依次向右滑动
  60.             // 入队之前进行比较判断，
  61.             while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
  62.                 // 剔除队列中<=arr[R]的元素，从尾部弹出队列
  63.                 qmax.pollLast();
  64.             }
  65.             qmax.addLast(R);
  67.             // 左窗口判断
  68.             // 左窗口过期位置的数弹出  R-W为窗口的过期下标
  69.             if (qmax.peekFirst() == R - w) {
  70.                 qmax.pollFirst();
  71.             }
  73.             // 大小收集判断
  74.             // 判断是否形成一个正常大小W的窗口
  75.             if (R >= w - 1) {
  76.                 // 形成窗口的时候才会收集答案
  77.                 res[index++] = arr[qmax.peekFirst()];
  78.             }
  79.         }
  80.         return res;
  81.     }
  83.     // for test
  84.     public static int[] generateRandomArray(int maxSize, int maxValue) {
  85.         int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
  86.         for (int i = 0; i < arr.length; i++) {
  87.             arr[i] = (int) (Math.random() * (maxValue + 1));
  88.         }
  89.         return arr;
  90.     }
  92.     // for test
  93.     public static boolean isEqual(int[] arr1, int[] arr2) {
  94.         if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
  95.             return false;
  96.         }
  97.         if (arr1 == null && arr2 == null) {
  98.             return true;
  99.         }
  100.         if (arr1.length != arr2.length) {
  101.             return false;
  102.         }
  103.         for (int i = 0; i < arr1.length; i++) {
  104.             if (arr1[i] != arr2[i]) {
  105.                 return false;
  106.             }
  107.         }
  108.         return true;
  109.     }
  111.     public static void main(String[] args) {
  112.         int testTime = 100000;
  113.         int maxSize = 100;
  114.         int maxValue = 100;
  115.         System.out.println("test begin");
  116.         for (int i = 0; i < testTime; i++) {
  117.             int[] arr = generateRandomArray(maxSize, maxValue);
  118.             int w = (int) (Math.random() * (arr.length + 1));
  119.             int[] ans1 = getMaxWindow(arr, w);
  120.             int[] ans2 = right(arr, w);
  121.             if (!isEqual(ans1, ans2)) {
  122.                 System.out.println("Oops!");
  123.             }
  124.         }
  125.         System.out.println("test finish");
  126.     }
  127. }

题目2：

给定一个整型数组arr，和一个整数 sum，某个arr中的子数组sub，如果想达标，必须满足： 子数组一定是连续的，sub中最大值-sub最小值<=sum，返回arr中达标子数组的数量。
（1）一个范围上达标，则内部子数组都达标。

  1. import java.util.LinkedList;
  3. public class Code02_AllLessNumSubArray {
  5.     // 方式1.暴力方法 时间复杂度 O(Math.pow(N,3))  N的三次方
  6.     public static int right(int[] arr, int sum) {
  7.         if (arr == null || arr.length == 0 || sum < 0) {
  8.             return 0;
  9.         }
  10.         int N = arr.length;
  11.         int count = 0;
  12.         // 枚举所有的子数组，
  13.             // [0,0][0,1][0,2][0,3][0,4]...[0,N-1]
  14.             // [1,1][1,2][1,3][1,4]...[1,N-1]
  15.             // [2,2][2,3][2,4][2,5]...[2,N-1]
  16.         for (int L = 0; L < N; L++) {     // L 所有子数组的开始位置
  17.             for (int R = L; R < N; R++) { // R 所有以L开头的子数组结束位置
  18.                 // 遍历寻找子数组[L,R]上的最大值和最小值
  19.                 int max = arr[L];
  20.                 int min = arr[L];
  21.                 for (int i = L + 1; i <= R; i++) {
  22.                     max = Math.max(max, arr[i]);
  23.                     min = Math.min(min, arr[i]);
  24.                 }
  25.                 // 达标count++
  26.                 if (max - min <= sum) {
  27.                     count++;
  28.                 }
  29.             }
  30.         }
  31.         return count;
  32.     }
  34.     // 方法2：窗口最大值和最小值结构
  35.     public static int num(int[] arr, int sum) {
  36.         if (arr == null || arr.length == 0 || sum < 0) {
  37.             return 0;
  38.         }
  40.         int N = arr.length;
  41.         int count = 0;  // 达标个数
  42.         LinkedList<Integer> maxWindow = new LinkedList<>();  // 窗口内最大值的更新结构
  43.         LinkedList<Integer> minWindow = new LinkedList<>();  // 窗口内最小值的更新结构
  45.         int R = 0; // 不回退，
  46.         for (int L = 0; L < N; L++) {  // 窗口以0 ,1 ,2,3,4...N开头
  47.             // 窗口规定 [L,R)左开右闭
  48.             while (R < N) {  // R向右扩，直至初次不达标的时候停
  49.                 // 更新窗口内最大值结构
  50.                 while (!maxWindow.isEmpty() && arr[maxWindow.peekLast()] <= arr[R]) {
  51.                     maxWindow.pollLast();
  52.                 }
  53.                 maxWindow.addLast(R);
  54.                 // 更新窗口内最小值结构
  55.                 while (!minWindow.isEmpty() && arr[minWindow.peekLast()] >= arr[R]) {
  56.                     minWindow.pollLast();
  57.                 }
  58.                 minWindow.addLast(R);
  60.                 // 更新完之后判断是否达标，如果达标R继续右移，否则while终止
  61.                 if (arr[maxWindow.peekFirst()] - arr[minWindow.peekFirst()] > sum) {
  62.                     // 找到以L开头的窗口第一个不达标的位置
  63.                     break;
  64.                 } else {
  65.                     R++;
  66.                 }
  67.             }
  68.             // 计算窗口以L开头达标的数组个数
  69.             count += R - L;
  71.             // 窗口过期位置清除
  72.             if (maxWindow.peekFirst() == L) {
  73.                 maxWindow.pollFirst();
  74.             }
  75.             if (minWindow.peekFirst() == L) {
  76.                 minWindow.pollFirst();
  77.             }
  78.         }
  79.         return count;
  80.     }
  82.     // for test
  83.     public static int[] generateRandomArray(int maxLen, int maxValue) {
  84.         int len = (int) (Math.random() * (maxLen + 1));
  85.         int[] arr = new int[len];
  86.         for (int i = 0; i < len; i++) {
  87.             arr[i] = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));
  88.         }
  89.         return arr;
  90.     }
  92.     // for test
  93.     public static void printArray(int[] arr) {
  94.         if (arr != null) {
  95.             for (int i = 0; i < arr.length; i++) {
  96.                 System.out.print(arr[i] + " ");
  97.             }
  98.             System.out.println();
  99.         }
  100.     }
  102.     public static void main(String[] args) {
  103.         int maxLen = 100;
  104.         int maxValue = 200;
  105.         int testTime = 100000;
  106.         System.out.println("测试开始");
  107.         for (int i = 0; i < testTime; i++) {
  108.             int[] arr = generateRandomArray(maxLen, maxValue);
  109.             int sum = (int) (Math.random() * (maxValue + 1));
  110.             int ans1 = right(arr, sum);
  111.             int ans2 = num(arr, sum);
  112.             if (ans1 != ans2) {
  113.                 System.out.println("Oops!");
  114.                 printArray(arr);
  115.                 System.out.println(sum);
  116.                 System.out.println(ans1);
  117.                 System.out.println(ans2);
  118.                 break;
  119.             }
  120.         }
  121.         System.out.println("测试结束");
  123.     }
  125. }

题目3：

加油站的良好出发点问题

/**
 * 加油站的良好出发点问题。
 */
// 测试链接：https://leetcode.com/problems/gas-station
public class Code03_GasStation {

    // 这个方法的时间复杂度O(N)，额外空间复杂度O(N)
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        boolean[] good = goodArray(gas, cost);
        for (int i = 0; i < gas.length; i++) {
            if (good[i]) {
                return i;
            }
        }
        return -1;
    }

    public static boolean[] goodArray(int[] g, int[] c) {
        int N = g.length;
        int M = N << 1;
        int[] arr = new int[M];
        for (int i = 0; i < N; i++) {
            arr[i] = g[i] - c[i];
            arr[i + N] = g[i] - c[i];
        }
        // 前缀和数组  二倍
        for (int i = 1; i < M; i++) {
            arr[i] += arr[i - 1];
        }

        LinkedList<Integer> w = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            while (!w.isEmpty() && arr[w.peekLast()] >= arr[i]) {
                w.pollLast();
            }
            w.addLast(i);
        }
        boolean[] ans = new boolean[N];
        for (int offset = 0, i = 0, j = N; j < M; offset = arr[i++], j++) {
            if (arr[w.peekFirst()] - offset >= 0) {
                ans[i] = true;
            }
            if (w.peekFirst() == i) {
                w.pollFirst();
            }
            while (!w.isEmpty() && arr[w.peekLast()] >= arr[j]) {
                w.pollLast();
            }
            w.addLast(j);
        }
        return ans;
    }

}

滑动窗口解题模板

参考：

  1. 定义需要维护的变量，通常包括最小长度，最大长度，或者hash表，HashSet有序不重复
  2. 定义窗口的首位两端，循环滑动窗口
  3. 更新需要维护的变量值

  4. 窗口合法条件判断

    1. 如果是固定窗口，则使用 if判断当前窗口是否到达了指定长度，1）更新维护变量 2）窗口开始位置右移

    2. 如果是可变窗口，使用while对窗口进行合法性判断，1） 更新维护变量 2）不断移动窗口左指针直到窗口再次合法

      class Solution:
def problemName(self, s: str) -> int:
  # Step 1: 定义需要维护的变量们 (对于滑动窗口类题目，这些变量通常是最小长度，最大长度，或者哈希表)
  x, y = ..., ...
  # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  start = 0
  for end in range(len(s)):
      # Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
      x = new_x
      if condition:
          y = new_y
      '''
      ------------- 下面是两种情况，读者请根据题意二选1 -------------
      '''
      # Step 4 - 情况1
      # 如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否达到了限定长度 
      # 如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变, 
      # 左指针移动之前, 先更新Step 1定义的(部分或所有)维护变量 
      if 窗口长度达到了限定长度:
          # 更新 (部分或所有) 维护变量 
          # 窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变

      # Step 4 - 情况2
      # 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
      # 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
      # 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 
      while 不合法:
          # 更新 (部分或所有) 维护变量 
          # 不断移动窗口左指针直到窗口再次合法

  # Step 5: 返回答案
  return ...

643. 子数组最大平均数 固定窗口

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。 请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。任何误差小于 10-5 的答案都将被视为正确答案。

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        // 变量表示滑动窗口内累加和
        double sum = 0;
        // 窗口内最大平均值
        double max_avg = 0;

        int start = 0;

        // 固定窗口，使用if判断，更新需要维护的变量，窗口右移。
        for(int end = 0; end < nums.length; end++){
            sum += nums[end];
            if(end >= k-1){
                // 更新需要维护的变量 max_avg 和 sum
                if(start == 0){
                    max_avg = sum/k;
                } else {
                    max_avg = Math.max(max_avg, sum/k);
                }
                sum -= nums[start++];
            }
        }
        return max_avg;
    }
}

1695.删除子数组的最大得分 可变窗口

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之和 。 返回 只删除一个 子数组可获得的 最大得分 。 如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],…,a[r] ，那么它就是 a 的一个子数组。 示例1： 输入：nums = [4,2,4,5,6] 输出：17 解释：最优子数组是 [2,4,5,6] 示例2： 输入：nums = [5,2,1,2,5,2,1,2,5] 输出：8 解释：最优子数组是 [5,2,1] 或 [1,2,5]

class Solution {
    // 最大连续不重复子数组
    public int maximumUniqueSubarray(int[] nums) {
        int sum = 0;
        int max = 0;
        HashSet<Integer> set = new HashSet<Integer>();
        int start = 0;
        // 窗口开始滑动
        for (int end = 0; end<nums.length; end++){
            // 不满足窗口条件
            while(set.contains(nums[end])){
                set.remove(nums[start]);
                // 更新维持的可变参数，同时窗口右移
                sum -= nums[start++];
            }
            // 满足进入窗口需求
            set.add(nums[end]);
            sum += nums[end];
            max = Math.max(max, sum);
        }
        return max;
    }
}

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == "" || s==null){
            return 0;
        }
        int max = 0;
        Set set = new HashSet<Character>();
        int start = 0;
        for(int end = 0; end < s.length(); end++){
            // 不满足条件
            while(set.contains(s.charAt(end))){
                set.remove(s.charAt(start));
                start++;
            }
            set.add(s.charAt(end));
            max = Math.max(end - start + 1,max);
        }
        return max;
    }
}