标签： 二分查找

目标

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: nums =  [3,3,7,7,10,11,11]
输出: 10

说明:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

思路

有序整数数组 nums，除了一个元素仅出现一次，其余每个元素都会出现两次，返回这个只出现一次的元素。

直接循环异或每个元素，时间复杂度为 O(n)。

题目要求时间复杂度是 O(logn) 显然需要使用二分查找，但是问题在于如果当前元素与其前/后元素相等，那么我们应该排除哪边？

这道题使用二分法的关键就是意识到 中间元素下标的奇偶性 与其前后元素的相等关系 可以判断只出现一次的元素在中间元素的哪边。

如果不考虑这个唯一元素，数组元素的排列一定是 a a b b c c ……，

• 如果 mid 为偶数下标，nums[mid] == nums[mid + 1]
• 如果 mid 为奇数下标，nums[mid - 1] == nums[mid]

现在插入了一个唯一元素，那么该下标 后面 的关系变为：

• 如果 mid 为偶数下标，nums[mid - 1] == nums[mid]
• 如果 mid 为奇数下标，nums[mid] == nums[mid + 1]

根据任意一组关系就可以判断唯一元素下标在 mid 的左侧还是右侧了。当 mid 为偶数，比较 nums[mid] == nums[mid + 1]，如果不相等说明在左侧，当 mid 为奇数，比较 nums[mid - 1] == nums[mid]，如果不等说明在左侧。即相等需要舍弃左边，不等舍弃右边。

官网题解给出了优化细节，省略奇偶性判断，直接比较 mid 与 mid^1 两个元素，当 mid 为奇数时，mid^1 = mid - 1，当 mid 为偶数时， mid^1 = mid + 1。

官网题解还给出了一种判断方法，由于唯一元素的下标一定是偶数，因此可以二分查找偶数下标，唯一元素以及它右侧的所有偶数下标都满足 nums[mid] != nums[mid + 1]，我们只需要找到第一个满足条件的下标即可。查找的过程需要保证 mid 为偶数，这样判断才能成立，通常的做法是得到 mid 之后判断其奇偶性，如果是奇数则减一。这里同样也有个优化细节，即 mid - (mid & 1) 可以保证 mid 为偶数。

代码

/**
 * @date 2024-11-10 14:38
 */
public class SingleNonDuplicate540 {

    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            mid -= mid & 1;
            if (nums[mid] != nums[mid + 1]) {
                r = mid;
            } else {
                l = mid + 2;
            }
        }
        return nums[l];
    }

}

性能

目标

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。

每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。

示例 1：

输入：time = [1,2,3], totalTrips = 5
输出：3
解释：
- 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
  已完成的总旅途数为 1 + 0 + 0 = 1 。
- 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
  已完成的总旅途数为 2 + 1 + 0 = 3 。
- 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
  已完成的总旅途数为 3 + 1 + 1 = 5 。
所以总共完成至少 5 趟旅途的最少时间为 3 。

示例 2：

输入：time = [2], totalTrips = 1
输出：2
解释：
只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
所以完成 1 趟旅途的最少时间为 2 。

说明：

• 1 <= time.length <= 10^5
• 1 <= time[i], totalTrips <= 10^7

思路

一趟旅行可以选择 n 辆公交车，time[i] 表示第 i 辆公交完成旅途的时间，同一时间每辆公交车可以独立地运行，完成一趟旅途后立刻开始下一趟。问完成 totalTrips 次旅途最少需要花费多少时间。

使用二分法尝试最少花费的时间 least，完成旅途的次数为 sum(least/time[i])。查找的上界为 10^14（当只有一辆车，且它完成一趟旅行需要耗时 10^7，总共需要完成 10^7 趟旅行）。

可以优化的点是上下界的取值，我们可以求出公交车完成旅行所需时间的最大与最小值，假设所有公交完成时间均为最小值 min，那么平均每辆车需要完成 ⌈totalTrips / n⌉ 次旅途，时间的下界为⌈totalTrips / n⌉ * min，同理，上界为 ⌈totalTrips / n⌉ * max。

代码

/**
 * @date 2024-10-05 21:34
 */
public class MinimumTime2187 {

    public long minimumTime_v1(int[] time, int totalTrips) {
        int n = time.length;
        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int i : time) {
            min = Math.min(i, min);
            max = Math.max(i, max);
        }
        long average = ((long) totalTrips - 1) / n + 1;
        long l = average * min;
        long r = average * max;
        long m = l + (r - l) / 2;
        while (l <= r) {
            if (check(time, totalTrips, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

    public long minimumTime(int[] time, int totalTrips) {
        long l = 0L, r = 100000000000000L;
        long m = l + (r - l) / 2;
        while (l <= r) {
            if (check(time, totalTrips, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

    private boolean check(int[] time, int totalTrips, long least) {
        long cnt = 0L;
        for (int i : time) {
            cnt += least / i;
            if (cnt >= totalTrips) {
                return true;
            }
        }
        return false;
    }
}

性能

优化上下界并没有明显的差距，并且还增加了编码的复杂度。

目标

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。

每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。

• 例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。

返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。

生成的测试用例保证答案不超过 10^7 ，且 hour 的 小数点后最多存在两位数字 。

示例 1：

输入：dist = [1,3,2], hour = 6
输出：1
解释：速度为 1 时：
- 第 1 趟列车运行需要 1/1 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
- 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。
- 你将会恰好在第 6 小时到达。

示例 2：

输入：dist = [1,3,2], hour = 2.7
输出：3
解释：速度为 3 时：
- 第 1 趟列车运行需要 1/3 = 0.33333 小时。
- 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
- 你将会在第 2.66667 小时到达。

示例 3：

输入：dist = [1,3,2], hour = 1.9
输出：-1
解释：不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。

说明：

• n == dist.length
• 1 <= n <= 10^5
• 1 <= dist[i] <= 10^5
• 1 <= hour <= 10^9
• hours 中，小数点后最多存在两位数字

思路

从家到办公室需要依次乘坐 n 趟列车，列车只在整点发车，已知每趟车的行驶距离 dist[i]，问在给定通勤时间 hour 内到达办公室，列车的最低时速是多少，取正整数，如果无法按时到达返回 -1。

我们假设时速为 v，那么到达办公室的时间为 cost = Σ⌈dist[i]/v⌉ + dist[n-1]/v 前面 n - 1 趟车通勤时间需要考虑等车时间，所以要向上取整，最后一趟车则不需要向上取整。我们只需要满足cost <= hour 即可。由于时速需要取正整数，那么 v 也应该向上取整。

这道题的难点在于如何在 v 未知的情况下，向上取整后再求和，没办法直接计算。只能搜索解空间了，我们可以估算出 v 的取值范围，然后使用二分查找代入式子计算并与 hour 比较。v 的下界为 Σdist[i]/hour，上界是 max(dist[i]) * 100，这相当于是一趟车最大的距离除以最小的时间，如果这个速度还赶不上，那就赶不上了。

求和的时间复杂度为 O(n)，n 最大 10^5 ，距离最大 10^5 有可能溢出，应使用 long 类型。二分查找的复杂度为 O(nlogv)，v 最大值为 10^10， log2(10^10) ≈ 33.2，总的规模为 10 ^ 6 可行。

代码

/**
 * @date 2024-10-02 21:44
 */
public class MinSpeedOnTime1870 {

    public int minSpeedOnTime(int[] dist, double hour) {
        long sum = 0;
        for (int value : dist) {
            sum += value;
        }
        int v = (int) Math.ceil(sum / hour - 0.5);
        long l = v, r = 200 * sum, m = l + (r - l) / 2;
        while (l <= r) {
            if (check(dist, hour, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l > 200 * sum ? -1 : (int)l;
    }

    private boolean check(int[] dist, double hour, long m) {
        int n = dist.length;
        double cost = 0;
        for (int i = 0; i < n - 1; i++) {
            cost += Math.ceil((double) dist[i] / m);
        }
        cost += (double) dist[n - 1] / m;
        return cost <= hour;
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 nums 。

一开始，所有下标都没有被标记。你可以执行以下操作任意次：

• 选择两个 互不相同且未标记 的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。

请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。

示例 1：

输入：nums = [3,5,2,4]
输出：2
解释：第一次操作中，选择 i = 2 和 j = 1 ，操作可以执行的原因是 2 * nums[2] <= nums[1] ，标记下标 2 和 1 。
没有其他更多可执行的操作，所以答案为 2 。

示例 2：

输入：nums = [9,2,5,4]
输出：4
解释：第一次操作中，选择 i = 3 和 j = 0 ，操作可以执行的原因是 2 * nums[3] <= nums[0] ，标记下标 3 和 0 。
第二次操作中，选择 i = 1 和 j = 2 ，操作可以执行的原因是 2 * nums[1] <= nums[2] ，标记下标 1 和 2 。
没有其他更多可执行的操作，所以答案为 4 。

示例 3：

输入：nums = [7,6,8]
输出：0
解释：没有任何可以执行的操作，所以答案为 0 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

提示：

• Think about how to check that performing k operations is possible.
• To perform k operations, it’s optimal to use the smallest k elements and the largest k elements and think about how to match them.
• It’s optimal to match the ith smallest number with the k-i + 1 largest number.
• Now we need to binary search on the answer and find the greatest possible valid k.

思路

有一个数组 nums，每一次操作我们可以标记数组中未被标记的两个数，要求其中一个数的两倍小于等于另一个数。问经过任意次操作，最多可以标记多少个数。

题目与下标无关，可以先排序。使用双指针 l r 从前往后找到第一个大于等于其两倍的数 p。然后 l+1 r 继续向后搜索，直到 l 到达 p，这时将 l 赋值为 r，并且赋值 r = r + 1，继续前面的算法。 应该使用一个数组记录是否已标记，当 l 第一次到达 p 时，应跳转到之前 r 未被标记的下标。

这种贪心策略也是不对的，对于示例2，排序后的数组为 2 4 5 9。如果优先标记 2 4 后面就不能再标记了，而如果先标记 2 5 我们还可以标记 4 9。

那如果我们倒过来考虑呢？从后往前找试试。反过来也不对，例如 10 10 40 100 如果先标记 40 100 前面就不能再标记了。

这样一来我们不知道满足条件后是否应该标记，需要搜索解空间看看哪个最大。回溯搜索相当于搜索n叉树 O(n^n)，如果不进行剪枝或者记忆的话肯定超时。如果考虑动态规划，状态又比较多，取决于元素是否被标记。

看了提示，匹配策略一定是前 k 个小的 small[i] 与后 k 个大的 big[i] 匹配。还是上面的例子 2 4 | 5 9 10 10 | 40 100 最优的匹配方式就是 2 5 4 9 10 40 10 100。现在问题就变成了找出最大的 k。使用二分法查找满足条件的最大 k，然后返回 2k 就是答案。

这道题卡住的点是没想清楚匹配方式。先入为主地以滑动窗口的方式匹配，连续地比较，匹配第一个能够匹配的，这种策略是不对的。

更优的解法是直接用双指针遍历，因为二分查找的判断复杂度为O(k)，整体是O(klogn)，不如双指针的O(n)。

代码

/**
 * @date 2024-09-12 9:14
 */
public class MaxNumOfMarkedIndices2576 {

    /**
     * 排序的复杂度O(nlogn) 双指针匹配的复杂度O((n + 1) / 2)
     */
    public int maxNumOfMarkedIndices_v1(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int rs = (n + 1) / 2;
        int l = 0;
        for (int r = rs; r < n; r++) {
            if (nums[l] * 2 <= nums[r]) {
                l++;
            }
        }
        return 2 * l;
    }

    /**
     * 排序的复杂度O(nlogn) 二分查找复杂度O(klogn) 其中判断的复杂度O(k) k最坏的情况下取n/2
     */
    public int maxNumOfMarkedIndices(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int l = 0, r = n / 2, k = l + (r - l) / 2;
        while (l <= r) {
            if (check(nums, k)) {
                l = k + 1;
            } else {
                r = k - 1;
            }
            k = l + (r - l) / 2;
        }
        return 2 * r;
    }

    public boolean check(int[] nums, int k) {
        int n = nums.length;
        for (int i = 0; i < k; i++) {
            if (nums[i] * 2 > nums[n - k + i]) {
                return false;
            }
        }
        return true;
    }

}

性能

二分查找

双指针

目标

在 X轴 上有一些奖品。给你一个整数数组 prizePositions ，它按照 非递减 顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。

你可以选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。

• 比方说 k = 2 ，你可以选择线段 [1, 3] 和 [2, 4] ，你可以获得满足 1 <= prizePositions[i] <= 3 或者 2 <= prizePositions[i] <= 4 的所有奖品 i 。

请你返回在选择两个最优线段的前提下，可以获得的 最多 奖品数目。

示例 1：

输入：prizePositions = [1,1,2,2,3,3,5], k = 2
输出：7
解释：这个例子中，你可以选择线段 [1, 3] 和 [3, 5] ，获得 7 个奖品。

示例 2：

输入：prizePositions = [1,2,3,4], k = 0
输出：2
解释：这个例子中，一个选择是选择线段 [3, 3] 和 [4, 4] ，获得 2 个奖品。

说明：

• 1 <= prizePositions.length <= 10^5
• 1 <= prizePositions[i] <= 10^9
• 0 <= k <= 10^9
• prizePositions 有序非递减。

思路

x轴的一些整数坐标上放有奖品，相同坐标点上可能有多个奖品。已知所有奖品所在坐标从小到大排序后的数组 prizePositions，问使用两个长度为k的线段最多能覆盖多少个奖品。线段可以相交，但相交区间内的奖品仅计数一次，线段端点处的奖品也计入总数。

最直观的想法是使用滑动窗口，固定区间长度，然后求能够覆盖的最多奖品数。但我们需要的是两个线段所能覆盖的最多奖品，能否记录下第一次求得的区间范围，然后在范围之外（两个线段尽量不相交才能覆盖更多奖品）在用相同的方法求次最多的奖品数。这看上去似乎可行，但具体写完之后会发现一些问题。

• 如果存在多个最大区间如何处理？可以参考下图，k取3的情况，不同的选择直接影响另一线段的取值。可以用一个列表记录区间范围，然后分别对这些区间范围之外的区间执行同样的算法？时间复杂度为 O(m * l)，m 为最大线段个数，l 为区间长度。

  

• 就算上面的复杂度可以接受，两个线段获得最多奖品，一定要其中一个线段覆盖最多的奖品吗？这个是不必要的。参考下图，k取2的情况：

  

针对这道题，这种贪心策略是不行的，局部最优解并不一定是全局最优解。现在我们没有一个明确的目标，最优的线段该如何取？如果我们同时滑动两个窗口呢？暴力写法是先固定一个，然后滑动另一个。时间复杂度为 O(n^2)，肯定超时。我们发现这里面有重复的子问题，定义 num[i] 表示以 prizePositions[i] 为起点长度为 k 的线段所能覆盖的奖品数。然后再用一个 max[i] 表示起点大于等于 prizePositions[i] 长度为 k 的线段所能覆盖的最大奖品数。这样我们就能以 O(1) 的复杂度取到固定一个窗口之后，另一个窗口的最大值。枚举固定窗口求出最大值即可。

写完之后发现，保存 num[i] 是不必要的，它只用来更新当前的 max[i]。

滑动窗口有两种写法，枚举左边界，循环内部直接到达可能的最右边界。另一种写法是枚举右边界，如果条件不满足，更新左边界直到满足条件。注意确保不要越界。

官网题解提供了二分法的解法，确实遇到有序数组就要想到二分法，但是这里二分找什么呢？大概是二分找所能覆盖的左边界，然后还是动态规划求不超过左边界的另一线段所能覆盖的最大值。官方题解这个解法的java版本好像是其它题目的，给错答案了。

代码

/**
 * @date 2024-09-11 8:57
 */
public class MaximizeWin2555 {

    public int maximizeWin_v1(int[] prizePositions, int k) {
        int n = prizePositions.length;
        if (k * 2 + 1 >= prizePositions[n - 1] - prizePositions[0]) {
            return n;
        }
        int res = 1;
        int[] max = new int[n + 1];
        int l = n - 1;
        for (int r = n - 1; r >= 0; r--) {
            while (l >= 0 && prizePositions[r] - prizePositions[l] <= k) {
                max[l] = Math.max(r - l + 1, max[l + 1]);
                res = Math.max(res, r - l + 1 + max[r + 1]);
                l--;
            }
        }
        return res;
    }

}

性能

目标

一位老师正在出一场由 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' 。

说明：

• n == answerKey.length
• 1 <= n <= 5 * 10^4
• answerKey[i] 要么是 'T' ，要么是 'F'
• 1 <= k <= n

思路

有一个字符串 answerKey 由 T 或 F 组成, 允许我们执行 k 次操作，每次操作可以将字符串中的 T 改为 F 或者 F 改为 T。问 T 或 F 可能的最大连续个数。

这道题没有做出来，想着使用动态规划去做，但是没有找到合适的状态定义。比如 dp[i][j][k] 表示 [0,i] 以 T 或 F 结尾剩余操作次数 k 时的最大连续个数。2 x 10^8 的存储空间肯定不行。

题解说是滑动窗口、或者 前缀和 + 二分查找，也有使用动态规划的。

这道题的难点在于想明白这 k 次操作必须统一，要么全部从 T 改为 F，要么全部从 F 改为 T，才能使连续个数最大。因为如果 T 的连续个数最多，并且存在将 T 改为 F 的操作，那么我们总可以撤回该操作，并将一个 F 改为 T（如果存在的话，如果不存在说明全是T，撤销操作也会加一） 使得连续个数至少加一。

网友题解中的动态规划是这样定义的 dp[i] 表示 [0,i] 中以 answerKey[i] 结尾的连续后缀个数。这里的前提就是遇到不连续的统一从 T 改为 F 或者 从 F 改为 T 使之连续，如果超过了可操作的次数，需要撤回最早的操作，使得当前后缀连续。后缀连续个数可以用当前下标减去最早进行操作的下标计算得到（使用链表保存操作的下标，获取链表head记录的下标后将其删，再将当前下标加入链表末尾）。在计算dp过程中记录其最大值即为最大连续个数。如果对这个动态规划进行存储优化，那就是滑动窗口。

寻找一个窗口，使得窗口内的 T 或者 F 个数小于等于 k，并且使 F 或者 T 的个数最大。滑动窗口的套路一般是枚举右边界，如果条件不满足，更新左边界直到条件满足。

二分的做法本质也是滑动窗口，枚举左边界，二分查找能够到达的最远右边界。

代码

/**
 * @date 2024-09-02 16:55
 */
public class MaxConsecutiveAnswers2024 {

    /**
     * 前缀和 + 二分查找
     * 其实本质也是滑动窗口，枚举左边界，二分查找最远的右边界
     * O(nlogn) 62ms
     */
    public int maxConsecutiveAnswers_v1(String answerKey, int k) {
        int n = answerKey.length();
        int[] prefix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (answerKey.charAt(i - 1) == 'T') {
                prefix[i] = prefix[i - 1] + 1;
            } else {
                prefix[i] = prefix[i - 1];
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            int l = i, r = n;
            int mid = l + (r - l) / 2;
            while (l <= r) {
                int num = mid - i + 1;
                int cnt = prefix[mid] - prefix[i - 1];
                if (num - cnt <= k || cnt <= k) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
                mid = l + (r - l) / 2;
            }
            res = Math.max(res, r - i + 1);
        }
        return res;
    }

    /**
     * 滑动窗口 O(n)
     * 21ms
     */
    public int maxConsecutiveAnswers(String answerKey, int k) {
        return Math.max(process(answerKey, k, 'T'), process(answerKey, k, 'F'));
    }

    public int process(String answerKey, int k, char turnTo) {
        int n = answerKey.length();
        int res = 0;
        List<Integer> optsIndex = new LinkedList<>();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (answerKey.charAt(i) != turnTo) {
                if (k > 0) {
                    k--;
                    optsIndex.add(i);
                    cnt++;
                } else {
                    cnt = i - optsIndex.remove(0);
                    optsIndex.add(i);
                }
            } else {
                cnt++;
            }
            res = Math.max(res, cnt);
        }
        return res;
    }

}

性能