前言

非定长滑动窗口的前提是保证单调性，无论是数量上的单调性还是数值上的单调性,最简单的单调性判断法就是数组里的数字都是正数/负数;值得注意的是,单调性包括窗口内的单调性和窗口外的单调性,一般保证窗口内的单调性居多

定长滑动窗口无需考虑单调性

定长滑动窗口

关键词是等号

D2. RGB Substring (hard version) 定长且匹配的模式固定且有限,枚举匹配模式

手串破环成链

面试题 17.17. 多次搜索

30. 串联所有单词的子串

187. 重复的DNA序列

438. 找到字符串中所有字母异位词

567. 字符串的排列

643. 子数组最大平均数 I

1052. 爱生气的书店老板

1343. 大小为 K 且平均值大于等于阈值的子数组数目

1456. 定长子串中元音的最大数目

1493. 删掉一个元素以后全为 1 的最长子数组

1876. 长度为三且各字符不同的子字符串

1984. 学生分数的最小差值

2134. 最少交换次数来组合所有的 1 II

2156. 查找给定哈希值的子串 乘法满足模运算,除法不满足

2269. 找到一个数字的 K 美丽值

不定长滑动窗口(最长,最短,最大,最小)

关键词是不大于/小于k的最长/最短,这里的最长最短是指窗口的长度,最大最小是指窗口中计算完的值

万万没想到之抓捕孔连顺有一个组合数的计算

最长的a或则b

面试题 05.03. 翻转数位

面试题 17.18. 最短超串

209. 长度最小的子数组

219. 存在重复元素 II

220. 存在重复元素 III

395. 至少有 K 个重复字符的最长子串

424. 替换后的最长重复字符

713. 乘积小于 K 的子数组

781. 森林中的兔子

904. 水果成篮

1004. 最大连续1的个数 III

1208. 尽可能使字符串相等

1234. 替换子串得到平衡字符串

1695. 删除子数组的最大得分

1763. 最长的美好子字符串

1838. 最高频元素的频数

1839. 所有元音按顺序排布的最长子字符串

2024. 考试的最大困扰度

2106. 摘水果来回折返,求最小值和加一个不满足条件的约束条件

2260. 必须拿起的最小连续卡牌数

2401. 最长优雅子数组

2730. 找到最长的半重复子字符串

2781. 最长合法子字符串的长度

2958. 最多 K 个重复元素的最长子数组

2968. 执行操作使频率分数最大 中位数是最短的

最好的假期-灵茶2023.1.10

两端处理

将两端转为中间,正难则反

1423. 可获得的最大点数

1658. 将 x 减到 0 的最小操作数

2516. 每种字符至少取 K 个

窗口内的最值

最值之差

单调队列 or TreeMap维护窗口内的最值

239. 滑动窗口最大值

594. 最长和谐子序列

1438. 绝对差不超过限制的最长连续子数组

最值个数

List[n]维护,时间复杂度为O(n)

2831. 找出最长等值子数组

滑动窗口的数量

一种是找到满足条件的和不满足条件的边缘,一种是枚举字符或则数目,一种是前缀和+map的思想

713. 乘积小于 K 的子数组

930. 和相同的二元子数组

992. K 个不同整数的子数组

1248. 统计「优美子数组」

1297. 子串的最大出现次数子串的数量>=子串的往右衍生的数量,因此子串数量,转为定长滑动窗口

1358. 包含所有三种字符的子字符串数目

2302. 统计得分小于 K 的子数组数目

2444. 统计定界子数组的数目

2537. 统计好子数组的数目

2762. 不间断子数组

2799. 统计完全子数组的数目

2953. 统计完全子字符串

2962. 统计最大元素出现至少 K 次的子数组

窗口外单调性

1574. 删除最短的子数组使剩余数组有序

2972. 统计移除递增子数组的数目 II