滑动窗口算法

滑动窗口算法的思路是这样：

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

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

3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。

同时，每次增加 left，我们都要更新一轮结果。

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

这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。

左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

 

leetcode题目：

2024. 考试的最大困扰度

一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。

老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。

（也就是连续出现 true 或者连续出现 false）。

给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。

除此以外，还给你一个整数 k ，表示你能进行以下 *** 作的最多次数：

每次 *** 作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i] 改为 'T' 或者 'F' ）。

请你返回在不超过 k 次 *** 作的情况下，最大 连续 'T' 或者 'F' 的数目。

示例 1：

输入：answerKey = "TTFF", k = 2
输出：4
解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。

总共有四个连续的 'T' 。

示例 2：

输入：answerKey = "TFFT", k = 1
输出：3
解释：我们可以将最前面的 'T' 换成 'F' ，得到 answerKey = "FFFT" 。

或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "TFFF" 。

两种情况下，都有三个连续的 'F' 。

示例 3：

输入：answerKey = "TTFTTFTT", k = 1
输出：5
解释：我们可以将第一个 'F' 换成 'T' ，得到 answerKey = "TTTTTFTT" 。

或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = "TTFTTTTT" 。

两种情况下，都有五个连续的 'T' 。

思路：

关键在于你怎么转变，一开始我想的是通过字符串变化，然后变化次数少于k；但是这样实际 *** 作比较麻烦，后面想到可以记录滑动窗口内的T数量和F数量，只要他们的最小者小于等于k，就可以继续滑动；

1.right右移，直到Tnum和Fnum的最小者>=k,记下最大值max
2.left右移，同时Tnum和Fnum跟着变化,num也跟着变化,直到Tnum和Fnum的最小者

代码：

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int left  = 0;
        int right = 0;
        int size  = answerKey.length();
        int max   = -1;
        int num   = 0;
        int Tnum  = 0;
        int Fnum  = 0;
        while(rightFnum?Fnum:Tnum)>k){
                if(num>max){
                max=num;
                }
                num++;
                while((Tnum>Fnum?Fnum:Tnum)>k){
                if(answerKey.charAt(left)== 'T'){
                    Tnum--;
                }else{
                    Fnum--;
                }
                num--;
                left++;
                }
                right++;
            }else{
            
            right++;
            num++;
            }
        }
        return max>num?max:num;
    }
}