滑动窗口的一些技巧

Stardust 2021年07月08日 31次浏览

滑动窗口在思路上是一个比较简单的方法,但是在某些情况下,其边界条件会变得非常棘手,这也是难点所在。

滑动窗口通常采用双指针实现,重点在于指针的初始化、结果的初始化、处理while的停止条件以及窗口内容的更新条件。

如果两个指针都对窗口内容有影响,这时不要把注意力同时放在两个指针上,否则两个指针互相影响会使得问题复杂化。

一般来说,滑动窗口的停止条件是右边界到达了数组的尽头:

while(right<n){
    ...
    right++;
}

然后,通过左指针来更新窗口。在此期间,不要再去考虑右指针,右指针在此次while中已经死了。

即使左指针不够用,宁可添加辅助变量,也尽量不要操作右指针。