滑动窗口是算法中一种重要的解题思想，通过分析力扣中的几道题目来学习滑动窗口的思想。
文章目录
一、更贴合笔试的滑动窗口综合题
1.1 题目分析
题目链接：220. 存在重复元素 III
题目描述：
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
示例一：
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
示例二：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false
题目分析：
根据题意，对于任意一个位置 i（假设其值为 u），我们其实是希望在下标范围为 [max(0, i-k), i] 内找到值范围在 [u-t, u+t] 的数。
一个朴素的想法是每次遍历到任意位置 i 的时候，往后检查 k 个元素，但这样做的复杂度是O(nk) 的，会超时。
显然我们需要优化「检查后面 k 个元素」这一过程。
我们希望使用一个「有序集合」去维护长度为 k 的滑动窗口内的数，该数据结构最好支持高效「查询」与「插入/删除」操作：
- 查询：能够在「有序集合」中应用「二分查找」，快速找到「小于等于的最大值」和「大于等于 u 的最小值」（即「有序集合」中的最接近 u 的数）。
- 插入/删除：在往「有序集合」添加或删除元素时，能够在低于线性的复杂度内完成（维持有序特性）。
或许你会想到近似 操作的 HashMap，但注意这里我们需要找的是符合abs(nums[i] - nums[j]) <= t 的两个值，nums[i] 与 nums[j] 并不一定相等，而 HashMap 无法很好的支持「范围查询」操作。
我们还会想到「树」结构。
例如 AVL，能够让我们在最坏为 O(logk)的复杂度内取得到最接近 u 的值是多少，但本题除了「查询」以外，还涉及频繁的「插入/删除」操作（随着我们遍历 nums 的元素，滑动窗口不断右移，我们需要不断的往「有序集合」中删除和添加元素）。
简单采用 AVL 树，会导致每次的插入删除操作都触发 AVL 的平衡调整，一次平衡调整会伴随着若干次的旋转。
而红黑树则很好解决了上述问题：将平衡调整引发的旋转的次数从「若干次」限制到「最多三次」。
因此，当「查询」动作和「插入/删除」动作频率相当时，更好的选择是使用「红黑树」。
也就是对应到 Java 中的 TreeSet 数据结构（基于红黑树，查找和插入都具有折半的效率）。
1.2 滑动窗口+有序集合
实现方面，我们在有序集合 TreeSet 中查找大于等于 x−t 的最小的元素 y，如果 y 存在，且 y ≤ x+t，我们就找到了一对符合条件的元素。完成检查后，我们将 x 插入到有序集合中，如果有序集合中元素数量超过了 k，我们将有序集合中最早被插入的元素删除即可。
其他细节：由于 nums 中的数较大，会存在 int 溢出问题，我们需要使用 long 来存储。
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
// TreeSet,基于红黑树，查找和插入都具有折半的效率
int n = nums.length;
TreeSet<Long> set = new TreeSet<Long>();
for (int i = 0; i < n; i++) {
Long ceiling = set.ceiling((long) nums[i] - (long) t); // 返回集合中大于或等于nums[i] - t的最小元素
if (ceiling != null && ceiling <= (long) nums[i] + (long) t) {
return true;
}
set.add((long) nums[i]); // 滑动窗口移动
if (i >= k) {
set.remove((long) nums[i - k]);
}
}
return false;
}
}
TreeSet函数：
ceiling(E e) 方法返回在这个集合中大于或者等于给定元素的最小元素，如果不存在这样的元素,返回 null.
floor(E e) 方法返回在这个集合中小于或者等于给定元素的最大元素，如果不存在这样的元素,返回null.
remove(Object O) 删除指定元素
add(Object O) 添加元素
1.3 桶排序
上述解法无法做到线性的原因是：我们需要在大小为 k 的滑动窗口所在的「有序集合」中找到与 u 接近的数。
如果我们能够将 k 个数字分到 个桶的话，那么我们就能 O(1) 的复杂度确定是否有 [u - t, u + t] 的数字（检查目标桶是否有元素）。
具体的做法为：令桶的大小为 size = t + 1，根据 u 计算所在桶编号：
- 如果已经存在该桶，说明前面已有
[u - t, u + t]范围的数字，返回 true - 如果不存在该桶，则检查相邻两个桶的元素是有
[u - t, u + t]范围的数字，如有 返回 true - 建立目标桶，并删除下标范围不在
[max(0, i-k), i]内的桶
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
// 桶排序
long size;
int n = nums.length;
Map<Long, Long> map = new HashMap<>();
size = t + 1L;
for (int i = 0; i < n; i++) {
long u = nums[i] * 1L;
long idx = getIdx(u, size);
// 目标桶已存在（桶不为空），说明前面已有 [u - t, u + t] 范围的数字
if (map.containsKey(idx)) return true;
// 检查相邻的桶
long l = idx - 1, r = idx + 1;
if (map.containsKey(l) && u - map.get(l) <= t) return true;
if (map.containsKey(r) && map.get(r) - u <= t) return true;
// 建立目标桶
map.put(idx, u);
// 移除下标范围不在 [max(0, i - k), i) 内的桶
if (i >= k) map.remove(getIdx(nums[i - k] * 1L, size));
}
return false;
}
long getIdx(long u, long size) {
return u >= 0 ? u / size : ((u + 1) / size) - 1;
}
}
理解 getIdx() 逻辑
-
为什么 size 需要对 t 进行 +1 操作？
目的是为了确保差值小于等于 t 的数能够落到一个桶中。举个 🌰，假设
[0,1,2,3]，t = 3，显然四个数都应该落在同一个桶。如果不对
t进行+1操作的话，那么[0,1,2]和[3]会被落到不同的桶中，那么为了解决这种错误，我们需要对t进行+1作为size。这样我们的数轴就能被分割成：
0 1 2 3 | 4 5 6 7 | 8 9 10 11 | 12 13 14 15 |…总结一下，令
size = t + 1的本质是因为差值为t两个数在数轴上相隔距离为t + 1，它们需要被落到同一个桶中。当明确了
size的大小之后，对于正数部分我们则有idx = nums[i] / size。 -
如何理解负数部分的逻辑？
由于我们处理正数的时候，处理了数值
0，因此我们负数部分是从-1开始的。还是我们上述 🌰，此时我们有
t = 3和size = t + 1 = 4。考虑
[-4,-3,-2,-1]的情况，它们应该落在一个桶中。如果直接复用
idx = nums[i] / size的话，[-4]和[-3,-2,-1]会被分到不同的桶中。根本原因是我们处理整数的时候，已经分掉了数值
0。这时候我们需要先对
nums[i]进行+1操作（即将负数部分在数轴上进行整体右移），即得到(nums[i] + 1) / size。这样一来负数部分与正数部分一样，可以被正常分割了。
但由于
0号桶已经被使用了，我们还需要在此基础上进行-1，相当于将负数部分的桶下标（idx）往左移，即得到((nums[i] + 1) / size) - 1。
二、字符串滑动窗口
2.1 题目分析
题目链接：424. 替换后的最长重复字符
题目描述：
给定一个字符串 s 和一个整数 k 。您可以选择字符串中的任意字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回 包含相同字母的最长子字符串的长度 。
示例一：
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。
示例二：
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
题目分析：
枚举字符串中的每一个位置作为右端点，然后找到其最远的左端点的位置，满足该区间内除了出现次数最多的那一类字符之外，剩余的字符（即非最长重复字符）数量不超过 k 个。
这样我们可以想到使用双指针维护这些区间，每次右指针右移，如果区间仍然满足条件，那么左指针不移动，否则左指针至多右移一格，保证区间长度不减小。
2.2 滑动窗口+双指针
class Solution {
public int characterReplacement(String s, int k) {
int[] num = new int[26];
int n = s.length();
int max = 0; // 字母出现最大次数
int left = 0, right = 0;
while (right < n) {
num[s.charAt(right) - 'A']++;
max = Math.max(max, num[s.charAt(right) - 'A']);
// len - 字母出现最大次数 > 替换次数K => len > 字母出现最大次数 + 替换次数k
// 则字母出现最大次数越大，len越大
if (right - left + 1 - max > k) {
num[s.charAt(left) - 'A']--;
left++;
}
right++;
}
return right - left;
}
}
三、滑动窗口转化问题
3.1 题目分析
题目链接：1052. 爱生气的书店老板
题目描述：
有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客的编号，所有这些顾客在第 i 分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。
当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。
请你返回 这一天营业下来，最多有多少客户能够感到满意 。
示例一：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
示例二：
输入：customers = [1], grumpy = [0], minutes = 1
输出：1
题目分析：
书店老板的秘密技巧只会将生气变为不生气，不生气仍然是不生气。
- 可以先将原来就满意的客户加入答案，同时将对应的
customers[i]变为0。 - 之后问题转化为，在
customers中找到连续一段长度为minutes的子数组，使得其总和最大。
3.2 滑动窗口 + 双指针
代码实现：
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
int res = 0;
for (int i = 0; i < customers.length; i++) {
if (grumpy[i] == 0) { // 将老板不生气的时间的顾客数加起来，且置为0
res += customers[i];
customers[i] = 0;
}
}
// 滑动窗口找剩余的顾客中最大的连续minutes的数
int cur = 0, max = 0;
for (int i = 0; i < customers.length; i++) {
cur += customers[i];
if (i >= minutes) { // 超过minutes,将最前面的删掉，窗口滑动
cur -= customers[i - minutes];
}
max = Math.max(max, cur); // max存储滑动窗口最大值
}
return res + max;
}
}
参考：
存在重复元素 III 官方题解
