【面试高频题】难度 1.5/5，常规滑动窗口运用题

题目描述

这是 LeetCode 上的 2024. 考试的最大困扰度 ，难度为 中等。

Tag : 「滑动窗口」、「双指针」

一位老师正在出一场由  道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是最大化有连续相同结果的题数。（也就是连续出现 true 或者连续出现 false）。

给你一个字符串   ，其中   是第  个问题的正确结果。除此以外，还给你一个整数 ，表示你能进行以下操作的最多次数：

每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 改为 'T' 或者 'F' ）。 请你返回在不超过  次操作的情况下，最大 连续 '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' 。

提示：

•  要么是 'T' ，要么是 'F'

滑动窗口

题目求修改次数不超过 的前提下，连续段 'T' 或 'F' 的最大长度。

等价于求一个包含 'F' 或者 'T' 的个数不超过 的最大长度窗口。

假定存在一个 int getCnt(char c) 函数，返回包含字符 c 数量不超过 的最大窗口长度，那么最终 max(getCnt('T'), getCnt('F')) 即是答案。

其中 getCnt 函数的实现可以使用「滑动窗口」：使用 和 分别代表窗口的左右端点， 为区间 中的字符 c 的数量，每次右端点 移动时，若满足 ，让 自增，当 时，使左端点 往右移动，同时更新 ，直到 区间恢复合法性（包含字符 c 的数量 不超过 个）。

代码：

class Solution {
    String s;
    int n, k;
    public int maxConsecutiveAnswers(String answerKey, int _k) {
        s = answerKey;
        n = s.length(); k = _k;
        return Math.max(getCnt('T'), getCnt('F'));
    }
    int getCnt(char c) {
        int ans = 0;
        for (int i = 0, j = 0, cnt = 0; i < n; i++) {
            if (s.charAt(i) == c) cnt++;
            while (cnt > k) {
                if (s.charAt(j) == c) cnt--;
                j++;
            }
            ans = Math.max(ans, i - j + 1);
        }
        return ans;
    }
}

• 时间复杂度：
• 空间复杂度：

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2024 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉