leetcode刷题笔记--最大滑动窗口

class Solution {
    public int longestOnes(int[] nums, int k) {
        int l = 0, r = 0;
        while (r < nums.length) {
            if (nums[r++] == 0) {
                k--;
            }
            if (k < 0 && nums[l++] == 0) {
                k++;
            }
        }
        return r - l;
    }
}

. - 力扣（LeetCode）

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

题解里找到的一个大佬的写法。记录一下

大佬的解释：

是的，这个写法维护的是一个只能单调变长的窗口。这种窗口经常出现在寻求”最大窗口“的问题中：因为要求的是”最大“，所以我们没有必要缩短窗口，于是代码就少了缩短窗口的部分；从另一个角度讲，本题里的K是消耗品，一旦透支，窗口就不能再增长了（也意味着如果K == 0还是有可能增长的）。所以K所代表的”资源“，通常是滑窗维护逻辑的核心，能这么写有两个先决条件：

• 固定一个左端点，K随窗口增大是单调变化的。据此我们可以推知长度为n的窗口如若已经”透支“（K < 0）了，那么长度大于n的也一定不符合条件；
• K的变化与数组元素有简单的算术关系。向窗口纳入（A[r++]）或移除（A[l++]）一个数组元素，可以在O(1)内更新K。

虽说有条件，但仔细排查会发现许多滑窗问题都可以满足。

. - 力扣（LeetCode）

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

这个题目就可以用两次上面的方法，分别求出最大连续T和最大连续F,再比较两者大小；

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int l=0,r=0;
        int k2=k;
        while(r<answerKey.length()){
            if(answerKey.charAt(r++)=='F') k--;
            if(k<0 && answerKey.charAt(l++)=='F') k++;
        }
        int temp=r-l;
        r=l=0;
        while(r<answerKey.length()){
            if(answerKey.charAt(r++)=='T') k2--;
            if(k2<0 && answerKey.charAt(l++)=='T') k2++;
        }
        return Math.max(r-l,temp);
    }
}

或者可以在窗口中同时记录T和F的个数，只要T和F的数量有一种小于k就行（这样就能把少的全变成多的）代码如下

class Solution {  
    public int maxConsecutiveAnswers(String answerKey, int k) {  
        int left = 0, right = 0;  
        int countF = 0; // Count of 'F's in the current window  
        int countT = 0; // Count of 'T's in the current window  
        int ans=0;
        while (right < answerKey.length()) {  
            // Expand the window by including answerKey[right]  
            if (answerKey.charAt(right) == 'F') {  
                countF++;  
            } else {  
                countT++;  
            }  
            right++;  
            
            // If we exceed k flips, we need to shrink the window  
            while (countF > k && countT > k) {  
                if (answerKey.charAt(left) == 'F') {  
                    countF--;  
                } else {  
                    countT--;  
                }  
                left++;  
            }
            ans = Math.max(ans,countF+countT);
        }  
        return ans;  
    }  
}