2024. 考试的最大困扰度

晚上不睡，白天崩溃。昨天周末去大学看发现9.1号刚好碰上新生入学了！

题目

LC每日一题，参考2024. 考试的最大困扰度 - 力扣（LeetCode）
，难度分1643 中等。

解题思路

• 滑动窗口：考虑过动态规划发现无法关联连续相同字符，想到贪心发现替换肯定是连续的不会分隔的肯定需要使用滑动窗口，关键点是怎么定义窗口范围，找规律可以发现如果窗口包含的两种字符数量有一种小于等于k则可把其全部替换为该字符满足题目条件可以计算为一个临时答案。

滑动窗口 9ms 94.38%

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        char[] cs = answerKey.toCharArray();
        int n = cs.length, res = 0;
        // 参考滑动窗口解法
        int l = 0, r = 0;// 窗口先增加r右指针，如果不满足min(tN,fN)<=k则l增加左指针开始右移
        int tN = 0, fN = 0; // 窗口当前F、N的数量
        while (r < n) { // 右指针遍历
            if(cs[r] == 'T') {
                tN++;
            } else {
                fN++;
            }
            while (l < r && tN > k && fN > k) { // 开始减小窗口 左指针右移动
                if (cs[l] == 'T') {
                    tN--;
                } else {
                    fN--;
                }
                l++;
            }
            res = Math.max(res, r - l + 1);// 当前窗口满足条件 计算一个备选结果
            r++;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n)，左右指针都最多遍历字符串一次，n 为字符串长度。
• 空间复杂度：O(1)，只使用了常量个变量空间。

2024-9-2