思路
对于求区间最值问题 ,最直观的解法还是通过滑动窗口/双指针来实现,通过对最大值的比较来输出结果。
对于双指针问题,最根本的问题其实就是对于左右指针移动的条件处理。
此题本质上就是通过右移右指针进行区间中0的计数【zeroNums】,当且0的个数大于K的时候进行左指针右移,右移左指针的时候得判断当前左指针元素是否为0,如果为0则zeroNums减1,否则不减。@1
代码
class Solution {
public int longestOnes(int[] A, int K) {
int zeroNums = 0,max = 0; // zeroNums 对区间中0元素的计数, max 为满足条件的最大长度
int left = 0, right = 0, len = A.length;
while(right<len){
if(A[right] == 1) {
right++;
}else if(A[right] == 0 && zeroNums < K){
zeroNums++;
right++;
}else{ // 此情况为满足条件@1 的时候的处理逻辑
if(A[left]==0){
zeroNums--;
left++;
}else{
left++;
}
max = Math.max(right-left+1, max);
}
max = Math.max(right-left, max); // 此部分为特殊边界处理。
}
return max;
}
}
优秀模板分享
def findSubArray(nums):
N = len(nums) # 数组/字符串长度
left, right = 0, 0 # 双指针,表示当前遍历的区间[left, right],闭区间
sums = 0 # 用于统计 子数组/子区间 是否有效,根据题目可能会改成求和/计数
res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
while 区间[left, right]不符合题意:# 此时需要一直移动左指针,直至找到一个符合题意的区间
sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
left += 1 # 真正的移动左指针,注意不能跟上面一行代码写反
# 到 while 结束时,我们找到了一个符合题意要求的 子数组/子串
res = max(res, right - left + 1) # 需要更新结果
right += 1 # 移动右指针,去探索新的区间
return res
作者:fuxuemingzhu
链接:https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/fen-xiang-hua-dong-chuang-kou-mo-ban-mia-f76z/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关题目引申
最大的连续1个数
思路
此题比较简短,在遍历数组的时候通过对1计数【ans】,当且仅当前元素为1的时候计数+1,否则重置为0,通过变量max来存放连续1最大的值。
代码
public class LC485 {
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0, ans = 0;
for(int num:nums){
if(num==1) {
ans++;
}else{
max = Math.max(ans, max); //@1
ans = 0;
}
}
return Math.max(ans, max); // 此处主要是为了解决边界条件,比如[1,1,1,1,1,1],因为并没有走到@1的逻辑,所以在最后输出的时候需要再次判断下
}
}