【滑动窗口与双指针】学习记录

是 【灵茶山艾府】佬的题单

一、定长滑动窗口

定长滑动窗口，每次移动窗口时移除窗口旧尾部元素的贡献，添加窗口新头部元素的贡献。

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

板子，每次移动窗口时若新头部元素为元音则计数加 $1$，若旧尾部元素为元音则计数减 $1$。

后面紧接着两道都是板子，不多赘述。

2090. 半径为 k 的子数组平均值

注意窗口的长度是 $2k+1$，不保证小于等于数组总长度 $n$。

2379. 得到 K 个黑块的最少涂色次数

转化为“黑色块最多（白色块最少）的窗口”。

1052. 爱生气的书店老板

窗口内全 $0$，每次移动窗口时若新头部元素为 $1$ 则加上对应贡献，若旧尾部元素为 $1$ 则减去对应贡献。

2841. 几乎唯一子数组的最大和

用 map 和一个计数器维护窗口内互不相同的元素的个数，另一个计数器维护窗口内元素和。满足“有至少 $m$ 个互不相同的元素”时用当前窗口内元素和更新答案。

下一题同理，互不相同元素数等于 $k$ 时更新答案。

1423. 可获得的最大点数

只拿两头的 $k$ 张转化为不拿中间的 $n-k$ 张，实际上是求长度为 $n-k$ 的窗口的最小元素和。

1652. 拆炸弹

维护窗口元素和后赋值给对应位置即可，使用取模计算循环性。

---

未完待续