【算法】滑动窗口三步走 (3)

窗口:窗口大小并不是固定的,可以不断扩容直到满足一定的条件;也可以不断缩小,直到找到一个满足条件的最小窗口;当然也可以是固定大小。

为了便于理解,这里采用的是字符串来讲解。但是对于数组其实也是一样的。滑动窗口算法的思路是这样:

我们在字符串 S 中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间 [left, right] 称为一个「窗口」。

我们先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的字符串符合要求(包含了 T 中的所有字符)。

此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的字符串不再符合要求(不包含 T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。

重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。

这个思路其实也不难,第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。

下面画图理解一下,needs 和 window 相当于计数器,分别记录 T 中字符出现次数和窗口中的相应字符的出现次数。

初始状态:

【算法】滑动窗口三步走

增加 right,直到窗口 [left, right] 包含了 T 中所有字符:

【算法】滑动窗口三步走

现在开始增加 left,缩小窗口 [left, right]。

【算法】滑动窗口三步走

直到窗口中的字符串不再符合要求,left 不再继续移动。

【算法】滑动窗口三步走

之后重复上述过程,先移动 right,再移动 left…… 直到 right 指针到达字符串 S 的末端,算法结束。

如果你能够理解上述过程,恭喜,你已经完全掌握了滑动窗口算法思想。至于如何具体到问题,如何得出此题的答案,都是编程问题,等会提供一套模板,理解一下就会了。

上述过程对于非固定大小的滑动窗口,可以简单地写出如下伪码框架:

int slidingWindow() { string s, t; // 在 s 中寻找 t 的「最小覆盖子串」 int left = 0, right = 0; string res = s; while(right < s.size()) { window.add(s[right]); right++; // 如果符合要求,说明窗口构造完成,移动 left 缩小窗口 while (window 符合要求) { // 如果这个窗口的子串更短,则更新 res res = minLen(res, window); window.remove(s[left]); left++; } } return res; }

但是,对于固定窗口大小,可以总结如下:

int slidingWindow() { // 固定窗口大小为 k string s; // 在 s 中寻找窗口大小为 k 时的所包含最大元音字母个数 int right = 0; while(right < s.size()) { window.add(s[right]); right++; // 如果符合要求,说明窗口构造完成, if (right>=k) { // 这是已经是一个窗口了,根据条件做一些事情 // ... 可以计算窗口最大值等 // 最后不要忘记把 right -k 位置元素从窗口里面移除 } } return res; }

可以发现此时不需要依赖 left 指针了。因为窗口固定所以其实就没必要使用left,right 双指针来控制窗口的大小。

其次是对于窗口是固定的,可以轻易获取到 left 的位置,此处 left = right - k;

实际上,对于窗口的构造是很重要的。具体可以看下面的实例。

实例1 1208. 尽可能使字符串相等

给你两个长度相同的字符串,s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销(开销可能为 0),也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串,则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串,则返回 0。

示例 1:

输入:s = "abcd", t = "bcdf", cost = 3
输出:3
解释:s 中的 "abc" 可以变为 "bcd"。开销为 3,所以最大长度为 3。
示例 2:

输入:s = "abcd", t = "cdef", cost = 3
输出:1
解释:s 中的任一字符要想变成 t 中对应的字符,其开销都是 2。因此,最大长度为 1。
示例 3:

输入:s = "abcd", t = "acde", cost = 0
输出:1
解释:你无法作出任何改动,所以最大长度为 1。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpwyxf.html