对于每个r找到一个l使得【l,r】中0的个数小于等于m,当r右移的时候,l可能不动可能会跟着右移。当滑动窗口内黑色段的长度大于m时【清洗剂最多只能清洗m段】,l 需要右移。并随时更新当前窗口内的能获得的纯白色木板的最大长度和区间内黑色段的长度。
时间复杂度为O(n)。
import java.util.*;
public class Solution {
/**
*
* @param n int整型 长度为n的白木板 木板被等分成了n段
* @param m int整型 清洗剂最多只能清洗m段
* @param a int整型一维数组 长度为n的数组a,为1表示白色,为0表示黑色
* @return int整型
*/
public int solve (int n, int m, int[] a) {
int ans = 0;//能获得的纯白色木板的最大长度
int num = 0;//滑动窗口内黑色段的长度
int l = 0;//滑动窗口[l,r]的最左端l
for(int i = 0; i < n; i++){
num += (a[i] == 0 ? 1 : 0);
while(num > m){
num -= (a[l] == 0 ? 1 : 0);
l++;
}
ans = Math.max(ans, i - l + 1);
}
return ans;
}
}


京公网安备 11010502036488号