最大连续1的个数III(java实现)

力扣 1004. 最大连续1的个数 III

题目说明

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

1 <= A.length <= 20000
0 <= K <= A.length
A[i] 为 0 或 1

示例

例1

输入：A = [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

输入：A = [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。

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题典型的运用了滑动窗口，通过标记窗口前后端来获取最长（连续）1子数组，让我们来看看具体如何实现的吧。

作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/fen-xiang-hua-dong-chuang-kou-mo-ban-mia-f76z/

实现

public int longestOnes(int[] A, int K) {
        int result = 0;
        int front = 0,rear = 0;
        //定义窗口前端和后端

        while(rear<A.length){
            //窗口没有滑出数组时，持续扩展或者滑动

            if(A[rear]==0){
                if(K==0){
                    //遇到0且可替换数为0时，将前端的窗口收缩
                    while(A[front]==1){ front++; }
                    front++;
                }
                else{
                    //可替换值减少
                    K--;
                }
            }
            result = Math.max(result,++rear-front);
            //根据滑动窗口获取最大连续1个数
        }
        return result;
    }