济源建设企业网站公司/网站数据分析

经典例题

给你一个仅由大写英文字母组成的字符串，你可以将任意的字符替换成另一个字符，但最多可替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
 
输入：s = “AABABA”, k = 1
输出：4
解释：将中间的一个’B’替换为’A’,字符串变为 “AAAABA”。

 
 

滑窗模板

public int SlidingWindow(String s) {len = s.length();			// 串的长度int[] count = new int[N];	// 用于统计区间内的信息int L = 0, R = 0;			// 窗口边界，这是一个闭区间[L, R]int res = 0;				// 窗口最大宽度(最终结果)while (R < len) {count[s.charAt(R)]++;			// 修改统计值，因为R的移动改变了窗口while (区间不符合题意) {count[s.charAt(L)]--;		// 修改统计值，因为L的移动改变了窗口L++;						// 左指针被动移动（虫子的尾部）}res = Math.max(res, R - L + 1);		// 尝试更新resR++;								// 右指针主动移动（虫子的头部）}
}

 
 

模板说明

1. 这篇文章的作者（here）提出了一个比滑动窗口更加生动形象的名字，虫取法。像一只蠕动前行的毛毛虫，后脚不动前脚向前方伸去，前脚不动后脚被拖拽跟上。
2. 因此模板的核心思想就是：以右指针为驱动，拖着左指针向前走——右指针主动移动，探索新的区域；左指针被迫跟进，负责保证区间符合题意。
3. 右指针的移动是一个 固定 的动作，每次固定移动一步，因此在内层的那个while之外；左指针的移动是一个 被迫 的动作，每次移动的步数并不确定，因此在内层的那个while之中。

 
 

一些理解

1. 这里题目中，给出的可能是字符串/数组，将字符串转化为数组（toCharArray）会得到不小的性能优化哦
2. 滑窗的本质是一个合法区间，既然是区间，就涉及到了所谓双指针。其实，“双指针”这个说法过于宽泛，一般而言的双指针，通常是两个(甚至三个、四个)指针从整体的两侧边界向内收缩，可以认为两个指针的方向是「相向而行」；而滑动窗口，区间不倾向于收缩而是倾向于移动，可以认为两个指针的方向是「同向而行」

 
 

本题答案

>>> 1.count数组统计的是区间内每个字母出现的次数，并维护了出现次数最多的字母的出现次数maxCnt
>>> 2.关于区间的合法性，用了一个巧妙的判断：maxCnt + k < R - L + 1(🌟🌟🌟)
>>> 2.即(出现次数最多的字母的出现次数+容错次数即可替换次数k)都无法填满这个窗口(R-L+1)的话，则非法了>>> 3.还有一个小细节可能需要理解，就是内层while可以写成if
>>> 3.这是因为在本题中，可以保证由于R走了一步而导致到非法，L走一步就一定能纠正回来———天机在于maxCnt此时并未维护，while循环仅仅会执行一次

class Solution {public int characterReplacement(String s, int k) {int len = s.length();char[] charArr = s.toCharArray();int[] count = new int[26];int maxCnt = 0;int L = 0, R = 0;int res = 0;while (R < len) {count[charArr[R] - 'A']++;maxCnt = Math.max(maxCnt, count[charArr[R] - 'A']);while (maxCnt + k < R - L + 1) {count[charArr[L] - 'A']--;L++;}res = Math.max(res, R - L + 1);R++;}return res;}
}

 
 

更多内容

关于滑动窗口的更多内容请戳这里：《【图解算法】模板的优化与进阶——滑动窗口专题》

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

$END$