滑动窗口思想 面试算法高频题

基本思想

滑动窗口思想其实就是快慢型的特例

计算机网络中滑动窗口协议（Sliding Window Protocol），该协议是TCP实现流量控制等的核心策略之一。事实上在与流量控制、熔断、限流、超时等场景下都会首先从滑动窗口的角度来思考问题，例如hystrix、sentinel等框架都使用了这种思想。

什么是窗口的滑动：

• 窗口：窗口其实就是两个变量left和right之间的元素，也可以理解为一个区间。窗口大小可能固定，也可能变化，如果是固定大小的，那么自然要先确定窗口是否越界，再执行逻辑处理。如果不是固定的，就要先判断是否满足要求，再执行逻辑处理。

• 滑动：说明这个窗口是移动的，事实上移动的仍然是left和right两个变量，而不是序列中的元素。当变量移动的时，其中间的元素必然会发生变化，因此就有了这种不断滑动的效果。

在实际问题中，窗口大小不一定是固定的，我们可以思考两种场景：

• 固定窗口的滑动就是火车行驶这种大小不变的移动 。

• 可变的窗口就像两个老师带着一队学生外出，一个负责开路，一个负责断后，中间则是小朋友。两位老师之间的距离可能有时大有时小，但是整体窗口是不断滑动的。

根据窗口大小是否固定，可以造出两种类型的题：

• 如果是固定的，则一般会让你求哪个窗口的元素最大、最小、平均值、和最大、和最小等等类型的问题。

• 如果窗口是变的，则一般会让你求一个序列里最大、最小窗口是什么等等。

滑动窗口题目本身没有太高的思维含量，但是实际在解题的时候仍然会感觉比较吃力，主要原因有以下几点：

• 解题最终要落实到数组上，特别是边界处理上，这是容易晕的地方，稍有疏忽就难以得到准确的结果。

• 有些元素的比较、判断等比较麻烦，不仅要借助集合等工具，而且处理过程中还有一些技巧，如果不熟悉会导致解题难度非常大。

• 堆！我们在前面介绍过，堆结构非常适合在流数据中找固定区间内的最大、最小等问题。因此滑动窗口经常和堆一起使用可以完美解决很多复杂的问题。

那双指针和滑动窗口啥区别呢？根据性质我们可以看到，滑动窗口是双指针的一种类型，主要关注两个指针之间元素的情况，因此范围更小一些，而双指针的应用范围更大，题型也更多。

子数组最大平均数

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

其中 1<=k<=nums.length<=10^5。

• 典型滑动窗口；先读取k个元素，再逐步让窗口向前走。

public static double findMaxAverage(int[] nums, int k) {
    int len = nums.length;
    int widowSum = 0;
    if (k > nums.length || nums.length < 1 || k < 1) {
        return 0;
    }
    //   第一步 先求第一个窗口的和
    for (int i = 0; i < k; i++) {
        widowSum += nums[i];
    }

    //  第二步 ：遍历，每次右边增加一个，左边减去一个，重新计算窗口最大值
    int res = widowSum;
    for (int right = k; right < len; right++) {
        widowSum += nums[right] - nums[right - k];
        res = Math.max(res, widowSum);
    }
    return (double) res / k;
}

最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

• 从第 2 个元素开始，先定义[left,right)的区间来表示当前的递增区间，执行如下操作：

  • 如果当前遍历到的元素比它左边的那一个元素要严格大，right就增加；

  • 否则就将left跳到right的起始位置，重新开始计算。

public static int findLengthOfLCIS(int[] nums) {
    int left = 0, right = 0;
    int res = 0;
    while (right < nums.length) {
        //右侧的新元素比左侧的小，则重新开始记录left位置
        //该问题本质就是快慢指针，left就是slow指针
        if (right > 0 && nums[right - 1] >= nums[right]) {
            left = right;
        }
        right++;
        res = Math.max(res, right - left);
    }
    return res;
}

• 一边遍历，一边统计每个递增区间的长度，如果长度超过之前所有区间的长度

public static int findLengthOfLCIS(int[] nums) {
    int curLen = 1;//当前连续递增区间的长度
    int res = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i - 1] >= nums[i]) {
            //不满足要求，重新开始计数
            curLen = 1;
        } else {
            curLen++;
        }
        res = Math.max(curLen, res);
    }
    return res;
}

最长子串专题

无重复字符的最长子串

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

输入: s = "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

• 要找最长子串，必然要知道无重复字符串的首和尾，然后再从中确定最长的那个，因此至少两个指针才可以，这就想到了滑动窗口思想。

• 即使使用滑动窗口，深入分析会发现具体处理起来有多种方式。这里介绍一种经典的使用Map的思路。

public  int lengthOfLongestSubstring(String s) {
    if (s.length() == 0) return 0;
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    int max = 0;
    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        if (map.containsKey(s.charAt(right))) {
            left = Math.max(left, map.get(s.charAt(right)) + 1);
        }
        map.put(s.charAt(right), right);
        max = Math.max(max, right - left + 1);
    }
    return max;
}

最多包含两个不同字符的最长子串

给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t ，并返回该子串的长度

输入: "eceba"

输出: 3

解释: t 是 "ece"，长度为3。

• 怎么判断只有2个元素

• 移除的时候怎么知道移除谁，以及移除之后left是什么。

  del_idx = Collections.min(hashmap.values());

  left = del_idx + 1;

  • 这个 hashmap 包括不超过 3 个元素。这里还要考虑到要移除谁，所以我们要设计一下Hash的Key-Value的含义。我们把字符串里的字符都当做键，在窗口中的最右边的字符位置作为值。

public  int lengthOfLongestSubstringTwoDistinct(String s) {
    if (s.length() < 3) {
        return s.length();
    }
    int left = 0, right = 0;
    HashMap<Character, Integer> hashmap = new HashMap<>();
    int maxLen = 2;
    
    while (right < s.length()) {
    
        if (hashmap.size() < 3)
            hashmap.put(s.charAt(right), right++);
    
        // 如果大小达到了3个
        if (hashmap.size() == 3) {
            // 最左侧要删除的位置
            int del_idx = Collections.min(hashmap.values());
            hashmap.remove(s.charAt(del_idx));
            // 窗口left的新位置
            left = del_idx + 1;
        }
    
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

至多包含k个不同字符的最长子串

给定一个字符串 s，找出 至多 包含 k 个不同字符的最长子串T。

输入: s = "eceba", k = 2

输出: 3

解释: 则 T 为 "ece"，所以长度为 3。

• 只要将判断hash大小为2改成k就可以

public  int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (s.length() < k + 1) {
        return s.length();
    }
    int left = 0, right = 0;
    HashMap<Character, Integer> hashmap = new HashMap<>();
    int maxLen = k;
    while (right < s.length()) {
        if (hashmap.size() < k + 1)
            hashmap.put(s.charAt(right), right++);
        // 如果大小达到了k个
        if (hashmap.size() == k + 1) {
            int del_idx = Collections.min(hashmap.values());
            hashmap.remove(s.charAt(del_idx));
            // 窗口left的新位置
            left = del_idx + 1;
        }
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

长度最小的子数组

长度最小的子数组,给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

输入：target = 7, nums = [2,3,1,2,4,3]

输出：2

解释：子数组 [4,3] 是该条件下的长度最小的子数组。

• 先让元素不断入队，当入队元素和等于target时就记录一下此时队列的容量，如果队列元素之和大于target则开始出队， 直到小于target则再入队。如果出现等于target的情况，则记录一下此时队列的大小，之后继续先入队再出队。每当出现元素之和等于target时我们就保留容量最小的那个。

public int minSubArrayLen(int target, int[] nums) {
    int left = 0, right = 0, sum = 0, min = Integer.MAX_VALUE;
    while (right < nums.length) {
        sum += nums[right++];
        while (sum >= target) {
            min = Math.min(min, right - left);
            sum -= nums[left++];
        }
    }
    return min == Integer.MAX_VALUE ? 0 : min;
}

盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

输入：[1,8,6,2,5,4,8,3,7]

输出：49

解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

设两指针 i , j ，指向的水槽板高度分别为 h[i] , h[j] ，此状态下水槽面积为S(i,j) 。由于可容纳水的高度由两板中的 短板 决定，因此可得如下面积公式 ：

S(i,j)=min(h[i],h[j])×(j−i)

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度−1 变短：

• 若向内移动短板 ，水槽的短板min(h[i],h[j]) 可能变大，因此下个水槽的面积可能增大 。

• 若向内移动长板 ，水槽的短板min(h[i],h[j]) 不变或变小，因此下个水槽的面积一定变小 。

因此，只要初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

public int maxArea(int[] height) {
    int i = 0, j = height.length - 1, res = 0;
    while(i < j) {
        res = height[i] < height[j] ? 
        Math.max(res, (j - i) * height[i++]): 
        Math.max(res, (j - i) * height[j--]); 
    }
    return res;
}

寻找子串异位词

如果两个字符串仅仅是字母出现的位置不一样，则称两者相互为对方的一个排列，也称为异位词。

字符串的排列

给你两个字符串s1和s2 ，写一个函数来判断 s2是否包含 s1的排列。如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的子串 。其中s1和s2都只包含小写字母。

思路：

• 因为字符串s1的异位词长度一定是和s2字符串的长度一样的，所以很自然的想到可以以s1.length()为大小截图一个固定窗口，然后窗口一边向右移动，一边比较就行了。字母类型一样，每个字母出现的个数也是一样的。题目说s1和s2都仅限小写字母，因此我们可以创建一个大小为26的数组，每个位置就存储从a到z的个数，为了方便操作，索引我们使用index=s1.charAt(i) - 'a'来表示，这是处理字符串的常用技巧。此时窗口的right向右移动就是执行：charArray2[s2.charAt(right) - 'a']++;而left向右移动就是执行：int left = right - sLen1； charArray2[s2.charAt(left) - 'a']--;

public boolean checkInclusion(String s1, String s2) {
    int sLen1 = s1.length(), sLen2 = s2.length();
    if (sLen1 > sLen2) {
        return false;
    }
    int[] charArray1 = new int[26];
    int[] charArray2 = new int[26];
    //先读最前面的一段来判断。
    for (int i = 0; i < sLen1; ++i) {
        ++charArray1[s1.charAt(i) - 'a'];
        ++charArray2[s2.charAt(i) - 'a'];
    }

    if (Arrays.equals(charArray1, charArray2)) {
        return true;
    }
    for (int right = sLen1; right < sLen2; ++right) {
        charArray2[s2.charAt(right) - 'a']++;
        int left = right - sLen1;
        charArray2[s2.charAt(left) - 'a']--;
        if (Arrays.equals(charArray1, charArray2)) {
            return true;
        }
    }
    return false;
}

寻找字符串中的所有字母异位

找到字符串中所有字母异位词，给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。注意s和p仅包含小写字母。

输入: s = "cbaebabacd", p = "abc"

输出: [0,6]

解释:

起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。

起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

• 与上题 的唯一区别：需要用一个List，如果出现异位词，还要记录其开始位置，那直接将其add到list中就可以了

public List<Integer> findAnagrams(String s, String p) {
    int sLen = s.length(), pLen = p.length();
    if (sLen < pLen) {
        return new ArrayList<Integer>();
    }
    List<Integer> ans = new ArrayList<Integer>();
    int[] sCount = new int[26];
    int[] pCount = new int[26];
    //先分别初始化两个数组
    for (int i = 0; i < pLen; i++) {
        sCount[s.charAt(i) - 'a']++;
        pCount[p.charAt(i) - 'a']++;
    }
    if (Arrays.equals(sCount, pCount)) {
        ans.add(0);
    }

    for (int left = 0; left < sLen - pLen; left++) {
        sCount[s.charAt(left) - 'a']--;
        int right=left + pLen;
        sCount[s.charAt(right) - 'a']++;

        if (Arrays.equals(sCount, pCount)) {
            //上面left多减了一次，所以
            ans.add(left + 1);
        }
    }
    return ans;
}

堆&滑动窗口结合

堆的大小一般是有限的，而且能直接返回当前位置下的最大值或者最小值，该特征与滑动窗口结合解决特定场景问题。

Question：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位，返回滑动窗口中的最大值。

输入：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

• 对于最大值、K个最大这种场景，优先队列（堆）是首先应该考虑的思路。大根堆可以帮助我们实时维护一系列元素中的最大值。

• 本题初始时，我们将数组 nums 的前 k个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 (num,index)，表示元素num 在数组中的下标为index。

public int[] maxSlidingWindow(int[] nums, int k) {
       int n = nums.length;
       PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
           public int compare(int[] pair1, int[] pair2) {
               return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
           }
       });
       for (int i = 0; i < k; ++i) {
           pq.offer(new int[]{nums[i], i});
       }
       int[] ans = new int[n - k + 1];
       ans[0] = pq.peek()[0];
       for (int i = k; i < n; ++i) {
           pq.offer(new int[]{nums[i], i});
           // 过期的最大值会被及时清理 保证最大值有效性
           while (pq.peek()[1] <= i - k) {
               pq.poll();
           }
           ans[i - k + 1] = pq.peek()[0];
       }
       return ans;
   }