文章目录
滑动窗口
滑动窗口是一种解决区间、序列问题的思想，它的本质是同向运动双指针，窗口由left、right两个索引指针确定，left和right单调递增，对于涉及区间、序列、子串的最长、最短、最值问题，使用滑动窗口可以将时间复杂度降低一个数量级，例如从\(O(n^2)\)降为\(O(n)\)。但并不是所有问题都可以使用滑动窗口来解决的，实际上无法找到一个简明可行的方法或标准来判断任一个问题是否适用于滑动窗口，基本都是通过已有的经验进行归化和尝试才能确定。
无重复字符的最长子串
LeetCode 3. 无重复字符的最长子串
给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
这是个经典的滑动窗口问题，而且该题展示了一种性质，具有该性质的问题往往可以用滑动窗口解决。以abcabcab为例，枚举子串的每个起始位置，并观察它们的答案：
以 (a)bcabcbb 开始的答案为 (abc)abcbb；
以 a(b)cabcbb 开始的答案为 a(bca)bcbb；
以 ab(c)abcbb 开始的答案为 ab(cab)cbb；
以 abc(a)bcbb 开始的答案为 abc(abc)bb；
以 abca(b)cbb 开始的答案为 abca(bc)bb；
以 abcab(c)bb 开始的答案为 abcab(cb)b；
以 abcabc(b)b 开始的答案为 abcabc(b)b；
以 abcabcb(b) 开始的答案为 abcabcb(b)。
可以看出，对于两个起始位置left1和left2，如果left1<left2，无重复字符的最长子串的终止位置必定满足right1<=right2，这个性质十分适合滑动窗口。换句话说：对于某个区间或者序列问题，如果left1<left2，满足答案要求的right1<=right2总是成立，那么就可以使用滑动窗口来解决。
以left=right=0为起始窗口，如果right移动后窗口内没有重复字符，那么移动right即可，否则移动left，直到right到达边界。
在滑动的过程中，需要根据题目要去维护窗口的信息，对于该题而言，我们需要维护窗口内是否存在重复字符的情况，这可以通过哈希表实现：
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, right = 0;
int n = s.length();
if(n == 0) return 0;
int max = 1;
HashSet<Character> hash = new HashSet<>();
hash.add(s.charAt(0));
while(right <= n - 1)
{
while(right + 1 <= n - 1 && hash.contains(s.charAt(right + 1)))
{
hash.remove(s.charAt(left));
left++;
}
right++;
if(right >= n) break;
hash.add(s.charAt(right));
max = Math.max(max, right - left + 1);
}
return max;
}
}
至多包含两个不同字符的最长子串
LeetCode 159. 至多包含两个不同字符的最长子串
此题和上题类似，但对子串的要求不同，检验上题的性质是否成立：
以 (c)caabbb 开始的答案为 (ccaa)bbb;
以 c(c)aabbb 开始的答案为 c(caa)bbb;
以 cc(a)abbb 开始的答案为 cc(aabbb);
以 cca(a)bbb 开始的答案为 cca(abbb);
以 ccaa(b)bb 开始的答案为 ccaa(bbb);
以 ccaab(b)b 开始的答案为 ccaab(bb);
以 ccaabb(b) 开始的答案为 ccaabb(b)。
不难看出，性质成立，因此可以使用滑动窗口方法。
此题要维护的窗口信息是其中是否包含至多两个不同字符，使用字典即可。
class Solution {
private void mapAdd(HashMap<Character, Integer> map, Character key, Integer adding)
{
if(!map.containsKey(key))
{
map.put(key, adding);
return;
}
Integer v = map.get(key);
if(v + adding <= 0) map.remove(key);
else map.put(key, v + adding);
}
public int lengthOfLongestSubstringTwoDistinct(String s) {
int left = 0, right = 0, max = 1;
int n = s.length();
HashMap<Character, Integer> map = new HashMap<>();
mapAdd(map, s.charAt(0), 1);
while(right < n - 1)
{
char ch = s.charAt(right + 1);
if(map.size() >= 2 && !map.containsKey(ch))
{
mapAdd(map, s.charAt(left), -1);
left++;
}
else
{
mapAdd(map, ch, 1);
right++;
}
max = Math.max(max, right - left + 1);
}
return max;
}
}
对于LeetCode 340. 至多包含K个不同字符的最长子串，思路是一致的。
限制正整数元素和的最短子数组
LeetCode 209. 长度最小的子数组
给定一个含有n个正整数的数组nums和一个正整数target，找出nums中满足元素和大于或等于target的长度最小的子数组的长度。如果不存在这样的子数组，返回0。
以2 3 1 2 4 3为例，target=7：
以 (2) 3 1 2 4 3 开始的答案为 (2 3 1 2) 4 3;
以 2 (3) 1 2 4 3 开始的答案为 2 (3 1 2 4) 3;
以 2 3 (1) 2 4 3 开始的答案为 2 3 (1 2 4) 3;
以 2 3 1 (2) 4 3 开始的答案为 2 3 1 (2 4 3);
以 2 3 1 2 (4) 3 开始的答案为 2 3 1 2 (4 3);
以 2 3 1 2 4 (3) 开始无答案。
可以看出性质成立，因此可以使用滑动窗口方法，本题要维护的窗口信息是其中的元素总和。
注意该题限制了数组nums中的每个元素均为正整数，这保证了性质的成立，如果元素可能为负数，那么性质将不成立，此时不能使用滑动窗口解决。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, right = 0, sum = nums[0];
int n = nums.length;
int min = n + 1;
while(right <= n - 1)
{
if(sum >= target)
{
min = Math.min(min, right - left + 1);
sum -= nums[left];
left++;
}
else
{
right++;
if(right >= n) break;
sum += nums[right];
}
}
return min == n + 1 ? 0 : min;
}
}
最小覆盖子串
LeetCode 76. 最小覆盖子串
给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串 "" 。
这是一道Hard题，需要注意：题目要求的是s中涵盖t所有字符的长度最小的子串，但并没有要求该子串中的字符顺序，即对于t中的每种字符，子串中该字符的数量只要大于t中该字符的数量即可。
以s=ADOBECODEBANC, t=ABC为例：
以 (A)DOBECODEBANC 开始的答案为 (ADOBEC)ODEBANC;
以 A(D)OBECODEBANC 开始的答案为 A(DOBECODEBA)NC;
以 AD(O)(B)(E)(C)O... 开始的答案均以 ...A)NC作为终止位置;
以 ADOBEC(O)DEBANC 开始的答案为 ADOBEC(ODEBANC);
以 ADOBECO(D)(E)(B)ANC 开始的答案均以末尾作为终止位置;
以 ...(A)(N)(C) 开始无答案，因此最小子串为ADOBECODE(BANC)。
可以看出性质成立，因此可以使用滑动窗口解决。
此题需要维护窗口内每个字符的数量，注意到我们只关注t中的字符，存在于s中但不存在于t中的字符是无关紧要的，不需要记录，因此可以使用一个字典来保存t中字符的数量，判断子串是否涵盖t中所有字符的方法即枚举该字典，并判断对于t中的每种字符，字典中该字符的数量是否大于t中该字符的数量。
由于所求的是长度最小的子串，如果窗口不满足要求，移动right即可，如果窗口满足要求，移动left即可。
注意该题的解法抽象之后可以解决一类问题：对于某个序列A和序列B，求出序列B的某个最短或最长区间，使得该区间“覆盖”A中的每一个元素，这里“覆盖”的含义随题意而定，且是无序的。
class Solution {
private HashMap<Character, Integer> charCounts = new HashMap<>();
private void hashAdd(HashMap<Character, Integer> map, String t, Character ch, int adding)
{
if(!charCounts.containsKey(ch)) return;
if(!map.containsKey(ch))
{
map.put(ch, adding);
}
else
{
int val = map.get(ch);
if(val + adding <= 0)
{
map.remove(ch);
}
else
{
map.put(ch, val + adding);
}
}
}
private int uniqueCharCount(String t)
{
HashSet<Character> hash = new HashSet<>();
int count = 0;
for(int i = 0; i < t.length(); i++)
{
char ch = t.charAt(i);
if(!hash.contains(ch))
{
count++;
hash.add(ch);
charCounts.put(ch, 1);
}
else
{
charCounts.put(ch, charCounts.get(ch) + 1);
}
}
return count;
}
private boolean hashMatch(HashMap<Character, Integer> map, String t, int uchc)
{
for(Map.Entry<Character, Integer> entry : map.entrySet())
{
char ch = entry.getKey();
int count = charCounts.get(ch);
if(count > entry.getValue())
{
return false;
}
}
return map.size() == uchc;
}
public String minWindow(String s, String t) {
int left = 0, right = 0, n = s.length(), m = t.length();
int uchc = uniqueCharCount(t);
int minlen = n + 1;
String minstr = null;
HashMap<Character, Integer> hash = new HashMap<>();
hashAdd(hash, t, s.charAt(0), 1);
while(right <= n - 1)
{
if(hashMatch(hash, t, uchc))
{
if(right - left + 1 < minlen)
{
minlen = right - left + 1;
minstr = s.substring(left, right + 1);
}
hashAdd(hash, t, s.charAt(left), -1);
left++;
if(left > right) break;
}
else
{
right++;
if(right >= n) break;
hashAdd(hash, t, s.charAt(right), 1);
}
}
return minstr == null ? "" : minstr;
}
}
覆盖问题的最小区间
给定k个非递减排列的整数列表。找到一个最小区间，使得k个列表中的每个列表至少有一个数包含在其中。我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
此题是一道较难的Hard题，如果将其抽象化则可以简化并使用滑动窗口解决。将这k个整数列表看成一个以“列表”为元素的序列A，我们的目标即是在另一个序列B找出一个最短区间，使得该区间能“覆盖”A中的每一个元素，注意每个元素是一个列表，此处“覆盖”的含义为该区间包含该列表中的任何一个数。
这种抽象的难点在于：序列B应该如何定义？注意序列B中的每个元素是一个整数，但必须限制B中的元素范围，可以想到序列B只需包含序列A中每个列表的每个元素即可，因此我们可以求出序列A中所有数中的最小值Min和最大值Max，序列B的范围取[Min, Max]即可，为了判断序列B的某个区间是否“覆盖”A中的元素，需要记录每个数包含在A中的哪些元素（列表）当中，因此序列B可以用HashMap<Integer, List<Integer>>，键表示数，而键值表示A中包含该数的列表。
使用最小覆盖子串中的方法，再使用滑动窗口即可：
class Solution {
private void kmapAdd(HashMap<Integer, Integer> kmap, List<Integer> ks, int adding) {
if(ks == null) return;
for(Integer k : ks) {
int val = kmap.getOrDefault(k, 0) + adding;
if(val <= 0) kmap.remove(k);
else kmap.put(k, val);
}
}
public int[] smallestRange(List<List<Integer>> nums) {
HashMap<Integer, List<Integer>> map = new HashMap<>();
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
int n = nums.size();
for(int i = 0; i < n; i++) {
var list = nums.get(i);
for(Integer val : list) {
var mlist = map.getOrDefault(val, new ArrayList<Integer>());
mlist.add(i);
map.put(val, mlist);
min = Math.min(min, val);
max = Math.max(max, val);
}
}
int left = min, right = min;
int minleft = min, minright = max, minlen = max - min + 1;
HashMap<Integer, Integer> kmap = new HashMap<Integer, Integer>();
kmapAdd(kmap, map.get(min), 1);
while(right <= max) {
if(kmap.size() == n) {
if(right - left + 1 < minlen) {
minlen = right - left + 1;
minleft = left;
minright = right;
}
kmapAdd(kmap, map.get(left), -1);
left++;
} else {
right++;
if(right > max) break;
kmapAdd(kmap, map.get(right), 1);
}
}
return new int[] {minleft, minright};
}
}
找到字符串中所有字母异位词
LeetCode 438. 找到字符串中所有字母异位词
给定两个字符串s和p，找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词指由相同字母重排列形成的字符串（包括相同的字符串），s和p只包含小写字母。
以s=cbaebabacd，p=abc为例，只能找到如下子串：
以 (c)baebabacd 开始的答案为 (cba)ebabacd；
以 cbaeba(b)acd 开始的答案为 cbaeba(bac)d。
性质成立是显然的，需要维护的窗口信息是其中每种字符的数量，判断时只要每种字符的数量和字符串p中每种字符的数量相同即可，这么做的话和常规的题目没有明显区别，这里提出一个优化的方法：可以记录子串和字符串p的差异，由于s和p只包含小写字母，因此可以使用一个differs数组（长度为26，分别对应a-z）来记录子串和字符串p的字符数差异，如果differs数组元素均为0表示该子串和字符串p是异位的，进一步地可以维护一个整数differ表示differs数组中不为0的元素个数，更新differs时也更新differ即可，当differ为0时表示该子串和字符串p是异位的：
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int slen = s.length(), plen = p.length();
int left = 0, right = 0 + plen - 1;
List<Integer> res = new ArrayList<Integer>();
if(slen < plen) return res;
int[] differs = new int[26];
int differ = 0;
for(int i = left; i <= right; i++)
{
differs[s.charAt(i) - 'a']++;
}
for(int i = 0; i < plen; i++)
{
differs[p.charAt(i) - 'a']--;
}
for(int i = 0; i < 26; i++)
{
if(differs[i] != 0) differ++;
}
while(right <= slen - 1)
{
if(differ == 0) res.add(left);
int tmp = --differs[s.charAt(left) - 'a'];
if(tmp == 0) differ--;
else if(tmp == -1) differ++;
left++;
right++;
if(right >= slen) break;
tmp = ++differs[s.charAt(right) - 'a'];
if(tmp == 0) differ--;
else if(tmp == 1) differ++;
}
return res;
}
}
删除元素后的最长等值子数组
LeetCode 2831. 找出最长等值子数组
给你一个下标从0开始的整数数组nums和一个整数k。如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。从nums中删除最多k个元素后，返回可能的最长等值子数组的长度。子数组是数组中一个连续且可能为空的元素序列。
此题的难度在于允许你从nums中删除最多k个元素，直观上是无法使用滑动窗口的。考虑对元素进行分组，对于每一种元素，考虑其在nums中的位置，这些位置将构成一个序列，例如nums = [1, 3, 2, 3, 1 3]，可以得到如下元素的位置序列：
元素1：[0, 4]
元素2：[2]
元素3：[1, 3, 5]
如果允许删除任意个元素的话，最长等值子数组的长度即最长位置序列的长度，但只允许删除最多k个元素，就需要搜索位置序列中满足要求的某个区间。对位置序列P中的两个索引为i和j的元素，可知删除元素前以这两个元素为首末的区间长度为P[j] - P[i] + 1，而删除后该区间内的相同元素个数为j - i + 1，因此需要删除的元素个数为\((P[j] - P[]i] + 1) - (j - i + 1) = P[j] - P[i] + i - j\)。注意不能通过P[j] - P[i] - 1来计算需要删除的元素个数，因为索引i和索引j不一定相邻。
对于每个位置序列P，我们需要找出满足\(P[j] - P[i] + i - j \leq k\)的最长区间（即j - i + 1最大），这个最长区间即该元素的最长等值子数组，而这个子问题是可以通过滑动窗口求解的。
为了求出全局的最长等值子数组，处理每个元素对应的位置序列并取结果的最大值即可：
class Solution {
public int longestEqualSubarray(List<Integer> nums, int k) {
HashMap<Integer, ArrayList<Integer>> poss = new HashMap<>();
for(int i = 0; i < nums.size(); i++)
{
int val = nums.get(i);
if(!poss.containsKey(val))
{
poss.put(val, new ArrayList<Integer>());
}
poss.get(val).add(i);
}
int max = 0;
for(var key : poss.keySet())
{
var pos = poss.get(key);
int left = 0, right = 0;
int n = pos.size();
while(right <= n - 1)
{
int delnum = pos.get(right) - pos.get(left) - (right - left);
if(delnum > k)
{
left++;
}
else
{
max = Math.max(max, right - left + 1);
right++;
}
}
}
return max;
}
}
替换元素后的最长等值子数组
LeetCode 424. 替换后的最长重复字符
给你一个字符串s和一个整数k。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行k次。在执行上述操作后，返回包含相同字母的最长子字符串的长度。字符串s仅含大小英文字符。
此题和上题类似，对每个元素对应的位置序列使用滑动窗口求解再取最大值即可，位置序列中两个索引i和索引j的元素之间要替换的元素数量同样为\((P[j] - P[]i] + 1) - (j - i + 1) = P[j] - P[i] + i - j\)，但如果还剩下替换的次数，则可以用于替换索引i之前和索引j之后的紧邻的元素，同时考虑边界。
class Solution {
public int characterReplacement(String s, int k) {
HashMap<Character, List<Integer>> map = new HashMap<>();
for(int i = 0; i < s.length(); i++) {
var list = map.getOrDefault(s.charAt(i), new ArrayList<Integer>());
list.add(i);
map.put(s.charAt(i), list);
}
int max = 0;
for(var key : map.keySet()) {
var list = map.get(key);
int left = 0, right = 0;
while(right <= list.size() - 1) {
int vleft = list.get(left);
int vright = list.get(right);
int replacenum = (vright - vleft + 1)
- (right - left + 1);
if(replacenum <= k) {
max = Math.max(max, vright - vleft + 1
+ Math.min(k - replacenum, vleft + s.length() - vright - 1));
right++;
} else {
left++;
}
}
}
return max;
}
}
限制绝对差的最长子数组
LeetCode 1438.绝对差不超过限制的最长连续子数组
给你一个整数数组nums，和一个表示限制的整数limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于limit。如果不存在满足条件的子数组返回0。
此题的性质显然是成立的，难点在于窗口信息的维护，我们需要的信息是窗口内的元素绝对差，题目要求的是任意两个元素之间的绝对差必须小于或等于limit，这等价于窗口内元素最大值减去最小值小于或等于limit。因此本题要维护的窗口信息是窗口内元素的最大值和最小值，注意窗口在滑动的过程中会增加一个元素并移除一个元素，这会影响窗口内的最值，此时应该使用特殊的数据结构：有序集合（或大根堆+小根堆，或两个优先队列）。
Java中的有序集合可以使用TreeMap来实现，只要记录窗口中每个元素的数量即可，增加元素时数量+1，移除元素时数量-1，如果元素数量为0那么移除元素对应的键：
class Solution {
public int longestSubarray(int[] nums, int limit) {
int left = 0, right = 0;
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
int n = nums.length, res = 0;;
map.put(nums[0], 1);
while(right <= n - 1) {
if(map.lastKey() - map.firstKey() <= limit) {
res = Math.max(res, right - left + 1);
right++;
if(right >= n) break;
map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
} else {
map.put(nums[left], map.get(nums[left]) - 1);
if(map.get(nums[left]) == 0) map.remove(nums[left]);
left++;
}
}
return res;
}
}
限制乘积的子数组数量
给你一个整数数组nums和一个整数k，请你返回子数组内所有元素的乘积严格小于k的连续子数组的数目。
以nums=[10, 5, 2, 6]，k=100为例：
以 (1o) 5 2 6 开始的答案为 (10) 5 2 6 和 (10 5) 2 6；
以 10 (5) 2 6 开始的答案为 10 (5) 2 6 和 10 (5 2) 6 和 10 (5 2 6);
以 10 5 (2) 6 开始的答案为 10 5 (2) 6 和 10 5 (2 6)；
以 10 5 2 (6) 开始的答案为 10 5 2 (6)。
总共的数量为8。
此题比较特别，所要求的是数量而不是最长、最短子数组的长度，对于任一个起始位置，如果已经计算出满足要求的最长子数组，那么以该起始位置开始的所有满足要求的子数组必定已经被滑动窗口经过，因此我们可以将此题看成对最长子数组的长度的求解，并在这个过程中记录数量。
考虑限制乘积的最长子数组问题，性质显然是成立的。以left=right=0开始，维护窗口内的乘积，如果乘积严格小于k，移动right，否则移动left。另一特别之处在于其限制的是乘积的最大值，尽管要求解的是最长子数组，但越长的窗口越难以满足该要求，因此可能会出现left移动后超过right的情况，考虑nums=[1, 2, 3, 4, 5]，k = 1，不存在满足条件的子数组，left会不断地超过right，在这种情况下要重新设置right。
如何计算数量呢？对所有满足条件的子数组，以终止位置进行分组的话，只要窗口每次增加元素的时候计算以该元素终止的子数组数量，为了防止重复计算，每次只需计算包含该新增元素的子数组，并保证每个终止位置只被计算一次即可。当窗口增加元素之前，窗口内的乘积严格小于k，因此以此时窗口的最后一个元素终止且包含该元素的满足要求的子数组的数目为right - left + 1。
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int left = 0, right = 0, multi = nums[0];
int n = nums.length, count = 0;
while(right <= n - 1) {
if(multi < k) {
count += right - left + 1;
System.out.printf("%d,%d,%d\n", left, right, count);
right++;
if(right >= n) break;
multi *= nums[right];
} else {
multi /= nums[left];
left++;
if(left >= n) break;
if(left > right) {
right = left;
multi = nums[left];
}
}
}
return count;
}
}
使数组连续的最小操作数
LeetCode 2009. 使数组连续的最小操作数
给你一个整数数组nums。每一次操作中，你可以将nums中任意 一个元素替换成任意整数。
如果nums满足以下条件，那么它是连续的 ：
nums中所有元素都是互不相同的。
nums中最大元素与最小元素的差等于nums.length - 1。
请你返回使nums连续的最少操作次数。
这是一道Hard题，注意题目对连续的定义，相当于nums中的元素重排后可以构成一个公差为1的等差序列，显然nums中的重复元素必须被替换，考虑nums替换后最终的最小值为left，则最大值为left + n - 1，这里left是不确定的，显然要求操作数尽量少的情况下left必定大于等于nums替换前的最小元素，且小于等于nums替换前的最大元素，另一个不太直观的结论是操作数最少的情况下left必定是nums替换前的某一个元素，因此可以对left进行枚举。
一旦left固定，right也就固定了，此时nums中位于[left, right]的元素如果没有重复那么可以保留，如果重复则需要将多余的替换为缺少的元素，而那些并不位于[left, right]的元素，也需替换来补充缺少的元素。假设nums中位于[left, right]的相异元素有k种，为了补足我们需要执行n - k次操作。
为了使用滑动窗口，我们对nums进行去重和排序，随后枚举left，找到最小的n - k即可。
class Solution {
public int minOperations(int[] nums) {
int n = nums.length;
HashSet<Integer> set = new HashSet<>();
for(int i = 0; i < n; i++) set.add(nums[i]);
List<Integer> sorted = new ArrayList<>(set);
Collections.sort(sorted);
int m = sorted.size();
int left = 0, right = 0, min = n + 1;
while(left <= m - 1) {
int leftv = sorted.get(left);
int rightv = leftv + n - 1;
while(right <= m - 1 && sorted.get(right) <= rightv)
{
min = Math.min(min, n - (right - left + 1));
right++;
}
left++;
}
return min;
}
}
滑动窗口的最值
LeetCode 239. 滑动窗口最大值
给你一个整数数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
此题虽然涉及滑动窗口，但并不能使用滑动窗口方法来求解。本问题要快速求解一个固定长度的滑动窗口在滑动过程中的最大值，滑动窗口每次移动时都会移除第一个元素并增加一个新的元素，由于移除的元素可能是原先窗口的最值，而新加入的元素可能会成为新的最值，因此需要一种有序的数据结构，这便是有序集合（或优先队列，或大/小根堆，或单调队列，或单调栈）。
以单调队列为例，其保证两个性质：
（1）队列内仅包含窗口内的元素：队列内的元素一定在当前窗口内，但不能保证当前窗口内的每个元素一定在队列内，根据单调队列的顺序不同，总是可以确保窗口内的最大值或最小值总是在队列中。
（2）队列保持单调顺序：队列内的元素要么从小到大，要么从大到小。
以从队尾到队头递增顺序的单调队列为例，队尾是队列中的最小值，队头是队列中的最大值，要维护单调队列的两个性质，在窗口每次移动时，如果移除的元素恰为队头，那么将队头元素删除，并将新加入窗口的元素加入到队尾，为了保证单调性，将移除队列中所有小于该元素的元素。在这种模式下，可以保证队列中的最大值，即队头，总是窗口的最大值。
注意对于长度为k的窗口，前k-1个元素添加进队列时窗口还未形成，可将窗口的左边界索引初始化为left = 1 - k，这样右边界索引为right = left + k - 1 = 0恰好覆盖第一个元素。
该方法的时间复杂度为\(O(n)\)。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> queue = new LinkedList<>();
int wcount = n - (k - 1);
int[] maxs = new int[wcount];
for(int i = 1 - k; i < wcount; i++) {
int j = i + k - 1;
if(i > 0 && queue.peekFirst() == nums[i - 1]) {
queue.removeFirst();
}
while(!queue.isEmpty() && queue.peekLast() < nums[j]) {
queue.removeLast();
}
queue.addLast(nums[j]);
if(i >= 0) maxs[i] = queue.peekFirst();
}
return maxs;
}
}
滑动窗口的中位数
LeetCode 480. 滑动窗口中位数
给你一个数组nums，有一个长度为k的窗口从最左端滑动到最右端。窗口中有k个数，每次窗口向右移动1位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
此题和上题类似，但所要求的不是滑动窗口的最值而是中位数。求解中位数的关键在于将元素分为两半，一半较小，另一半较大，中位数根据较小一半的最大值和较大一半的最小值计算得到，滑动窗口移动时移除的元素和新增的元素都会对中位数造成影响，此时需要使用一种特殊的策略：对顶堆。
对顶堆本质上是两个堆，一个大根堆small和一个小根堆large，大根堆small保存较小的一半元素而小根堆large保存较大的一半元素，元素个数为偶数的情况下两个堆的元素数量相同，此时中位数即两个堆的堆顶元素的平均值。注意元素个数为奇数的情况下，如果我们约定small保存前\( \lceil \frac{n}{2} \rceil\)个较小的元素，而large保存其余\( \lfloor \frac{n}{2} \rfloor\)个较大的元素，那么small的元素将比large多一个，且中位数恰是small的堆顶元素。
本题的难点在于在滑动窗口移动的时候如何维护这两个堆，这包括两个问题：（1）如何将新增元素分配到合适的堆中，并保证两个堆的元素数量平衡。（2）如何在两个堆中删除因为滑动窗口移动而被移除的元素，并保证两个堆的元素数量平衡。
将对顶堆实现为这几个方法：insert(num)、erase(num)、getMedian()。
首先考虑第一个问题，即insert方法的实现，当滑动窗口移动时，我们只需增加一个元素，如果small和large均为空那么优先将该元素放入small中，如果small非空则将该元素和small的堆顶元素进行比较，如果大于堆顶元素则将该元素放入large中，否则放入small中。每次只增加一个元素，因此即便两个堆失衡，也只有以下两种情况：
（1）small元素比large多两个，此时将small的堆顶元素加入到large即可。
（2）small元素比large少一个，此时将large的堆顶元素加入到small即可。
接下来考虑第二个问题，即erase方法的实现，由于我们只能方便地移除堆顶元素，而非堆顶元素的移除是很麻烦的，因此对于某个要删除的元素，我们只能等待其到达堆顶后删除，并在此之前将其标记，这种手段称为延迟删除，延迟删除通常使用一个词典来实现，<key, val>表示元素key还需被删除val次。
为了便于编码，我们保证任意的insert、erase、getMedian操作执行后，两个堆的堆顶元素必定不需要延迟删除，这样的话实现getMedian方法计算中位数时就可以安全使用堆顶元素。为了保证该性质，我们实现prune方法，它不断删除堆顶中被标记为延迟删除的元素，直到堆顶元素不需要延迟删除。
注意向堆中增加或移除元素都可能会改变堆顶元素，因此每次增加或移除元素后都需要执行prune方法，即insert方法加入元素并调整后要执行prune方法，erase方法移除元素并调整后要执行prune方法，为此可以将调整过程和prune方法封装在一起，实现为makeBalance方法，由insert方法和erase方法调用makeBalance方法。
保证上述性质后，erase方法可以这样实现：如果要删除的元素既不是small的堆顶元素，也不是large的堆顶元素，那么标记该元素，增加词典中的待删除次数。如果要删除的元素是small的堆顶元素或者large的堆顶元素，同样标记该元素，并立即执行prune方法。
class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
DualHeap dh = new DualHeap(k);
for(int i = 0; i < k; i++) {
dh.insert(nums[i]);
}
double[] medians = new double[nums.length - k + 1];
medians[0] = dh.getMedian();
for(int i = 1; i < nums.length - k + 1; i++) {
int j = i + k - 1;
dh.insert(nums[j]);
dh.erase(nums[i - 1]);
medians[i] = dh.getMedian();
}
return medians;
}
}
class DualHeap {
//small为大根堆，large为小根堆
private PriorityQueue<Integer> small;
private PriorityQueue<Integer> large;
//两个堆的元素数量，不计入延迟删除的元素
private int smallSize;
private int largeSize;
//延迟删除词典
private HashMap<Integer, Integer> delayed;
//窗口元素数量，用于求中位数
private int k;
public DualHeap(int k) {
this.small = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
return num2.compareTo(num1);
}
});
this.large = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
return num1.compareTo(num2);
}
});
this.delayed = new HashMap<>();
this.k = k;
this.smallSize = 0;
this.largeSize = 0;
}
public double getMedian() {
if(k % 2 == 0) return ((double) small.peek() + large.peek()) / 2;
else return small.peek();
}
public void insert(int num) {
if(small.isEmpty())
{
small.offer(num);
smallSize++;
}
else if(num <= small.peek()) {
small.offer(num);
smallSize++;
} else {
large.offer(num);
largeSize++;
}
makeBalance();
}
private void makeBalance() {
if(smallSize == largeSize + 2) {
large.offer(small.poll());
smallSize--;
largeSize++;
prune(small);
} else if(smallSize == largeSize - 1) {
small.offer(large.poll());
smallSize++;
largeSize--;
prune(large);
}
}
private void prune(PriorityQueue<Integer> heap) {
while(!heap.isEmpty()) {
int num = heap.peek();
if(delayed.containsKey(num)) {
delayed.put(num, delayed.get(num) - 1);
if(delayed.get(num) == 0) {
delayed.remove(num);
}
heap.poll();
} else {
break;
}
}
}
public void erase(int num) {
delayed.put(num, delayed.getOrDefault(num, 0) + 1);
if(num == small.peek()) {
smallSize--;
prune(small);
} else if(num == large.peek()) {
largeSize--;
prune(large);
} else if(num < small.peek()) {
smallSize--;
} else if(num > small.peek()) {
largeSize--;
}
makeBalance();
}
}