欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Max Consecutive Ones III

程序员文章站 2024-03-06 09:57:55
...

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s. 

 

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

 

Note:

  1. 1 <= A.length <= 20000
  2. 0 <= K <= A.length
  3. A[i] is 0 or 1 

 

题目理解:

给定一个由0和1组成的数组,将其中的某K个0变成1之后,数组中存在的最长的连续的1有多长

解题思路:

用dp[i]表示到i位置为止,有多少个0,使用两个指针left和right,每次固定left,移动right,保证right - left <= K,记录最大的(right - left)。然后将left加1,继续移动right。right可以一直增加,因为如果right变小,那么(right - left)一定小于已经记录的最大值。

class Solution {
    public int longestOnes(int[] A, int K) {
        int len = A.length;
        int[] record = new int[len + 1];
        for(int i = 1; i < len + 1; i++){
            record[i] = record[i - 1];
            if(A[i - 1] == 0)
                record[i]++;
        }
        int left = 0, right = 0, res = 0;
        while(true){
            while(right < len && record[right + 1] - record[left] <= K)
                right++;
            res = Math.max(res, right - left);
            if(right == len)
                break;
            left++;
        }
        return res;
    }
}

 

相关标签: LeetCode