滑动窗口算法基本原理与实践
学过计算机网络的同学,都知道滑动窗口协议(Sliding Window Protocol),该协议是?TCP协议?的一种应用,用于网络数据传输时的流量控制,以避免拥塞的发生。该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认。因此该协议可以加速数据的传输,提高网络吞吐量。 滑动窗口算法其实和这个是一样的,只是用的地方场景不一样,可以根据需要调整窗口的大小,有时也可以是固定窗口大小。 滑动窗口算法(Sliding Window Algorithm)
简而言之,滑动窗口算法在一个特定大小的字符串或数组上进行操作,而不在整个字符串和数组上操作,这样就降低了问题的复杂度,从而也达到降低了循环的嵌套深度。其实这里就可以看出来滑动窗口主要应用在数组和字符串上。 基本示例如下图所示,设定滑动窗口(window)大小为 3,当滑动窗口每次划过数组时,计算当前滑动窗口中元素的和,得到结果 res。 可以用来解决一些查找满足一定条件的连续区间的性质(长度等)的问题。由于区间连续,因此当区间发生变化时,可以通过旧有的计算结果对搜索空间进行剪枝,这样便减少了重复计算,降低了时间复杂度。往往类似于“ 请找到满足 xx 的最 x 的区间(子串、子数组)的 xx ”这类问题都可以使用该方法进行解决。 需要注意的是,滑动窗口算法更多的是一种思想,而非某种数据结构的使用。? 滑动窗口法的大体框架在介绍滑动窗口的框架时候,大家先从字面理解下:
为了便于理解,这里采用的是字符串来讲解。但是对于数组其实也是一样的。滑动窗口算法的思路是这样:
这个思路其实也不难,第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。 下面画图理解一下,needs 和 window 相当于计数器,分别记录 T 中字符出现次数和窗口中的相应字符的出现次数。 初始状态: 增加 right,直到窗口 [left,right] 包含了 T 中所有字符: 现在开始增加 left,缩小窗口 [left,right]。 直到窗口中的字符串不再符合要求,left 不再继续移动。 之后重复上述过程,先移动 right,再移动 left…… 直到 right 指针到达字符串 S 的末端,算法结束。 如果你能够理解上述过程,恭喜,你已经完全掌握了滑动窗口算法思想。至于如何具体到问题,如何得出此题的答案,都是编程问题,等会提供一套模板,理解一下就会了。 上述过程对于非固定大小的滑动窗口,可以简单地写出如下伪码框架: 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; 但是,对于固定窗口大小,可以总结如下: 固定窗口大小为 k string s; 在 s 中寻找窗口大小为 k 时的所包含最大元音字母个数 int right = 0; 如果符合要求,说明窗口构造完成, if (right>=k) { 这是已经是一个窗口了,根据条件做一些事情 ... 可以计算窗口最大值等 最后不要忘记把 right -k 位置元素从窗口里面移除 } } return res; ? 可以发现此时不需要依赖 left 指针了。因为窗口固定所以其实就没必要使用left,right 双指针来控制窗口的大小。 其次是对于窗口是固定的,可以轻易获取到 left 的位置,此处 left =?right-k; 实际上,对于窗口的构造是很重要的。具体可以看下面的实例。 算法实例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",1)">
输出:1
解释:s 中的任一字符要想变成 t 中对应的字符,其开销都是 2。因此,最大长度为 1。
示例 3: 输入:s = "abcd",t = "acde",cost = 0
解释:你无法作出任何改动,所以最大长度为 1。?
代码class Solution { public int equalSubstring(String s,String t,int maxCost) { int sum = 0int res = 0; 这里跟前面总结的框架不一样的一个点就是,前面的框架是求最小窗口大小,这里是求最大窗口大小,大家要学会灵活变通。 239. 滑动窗口最大值给定一个数组 nums,有一个大小为?k?的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k?个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 进阶: 你能在线性时间复杂度内解决此题吗? 示例: 输入: nums = [1,3,-1,-3,5,6,7],和 k = 3 输出: [3,7] 解释: 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 提示: 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 1 <= k <= nums.length 解答:static int[] maxSlidingWindow(int[] nums,1)"> k) { int right =0int[] res = new int[nums.length -k +1]; int index=0; LinkedList<Integer> list = new LinkedList<>(); 这道题难度是困难。当然我们也会发现,这道题目和前面的非固定大小滑动窗口还是不一样的。 看了一道困难的题目后,接下来看一道中等难度的就会发现是小菜一碟。 1456. 定长子串中元音的最大数目给你字符串 s 和整数 k 。 请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。 英文中的 元音字母 为(a,e,i,o,u)。 示例 1: 输入:s = "abciiidef",k = 3
解释:子字符串 "iii" 包含 3 个元音字母。
示例 2: 输入:s = "aeiou",k = 2 输出:2 解释:任意长度为 2 的子字符串都包含 2 个元音字母。 示例 3: 输入:s = "leetcode",1)"> 解释:"lee"、"eet" 和 "ode" 都包含 2 个元音字母。 示例 4: 输入:s = "rhythms",k = 4 输出:0 解释:字符串 s 中不含任何元音字母。 示例 5: 输入:s = "tryhard",1)"> 输出:1 提示: 1 <= s.length <= 10^5
s 由小写英文字母组成
1 <= k <= s.length
解答int maxVowels(String s,1)">int max = 0 s.length()) { sum += isYuan(s.charAt(right)) ; right++; k) { max = Math.max(max,sum); sum -= isYuan(s.charAt(right-k)); } } max; } int isYuan(char s) { return s=='a' || s=='e' ||s=='i' ||s=='o' ||s=='u' ? 1:0; } } ? 参考文章 算法与数据结构(一):滑动窗口法总结? (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |