文章
问答
冒泡
LeetCode 每日一题

image.png

思路

对于求区间最值问题 ,最直观的解法还是通过滑动窗口/双指针来实现,通过对最大值的比较来输出结果。
对于双指针问题,最根本的问题其实就是对于左右指针移动的条件处理。
此题本质上就是通过右移右指针进行区间中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个数

image.png

思路

此题比较简短,在遍历数组的时候通过对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的逻辑,所以在最后输出的时候需要再次判断下
    }
}
数据结构与算法

关于作者

Kirago
个人站点 https://kiragoo.github.io/
获得点赞
文章被阅读