首页 > 其他 > 详细

Max Consecutive Ones III

时间:2020-01-31 01:02:44      阅读:78      评论:0      收藏:0      [点我收藏+]

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.

分析:
用两个指针: start, end. 不断往前移动end,当arr[end]是0的话,就增加count的个数。如果count的个数超过k,那么就往前移动start, 然后不断比较global_max和 end - start + 1.
 1 class Solution {
 2     public int longestOnes(int[] A, int K) {
 3         int zeroCount = 0, start = 0, res = 0;
 4         for (int end = 0; end < A.length; end++) {
 5             if (A[end] == 0) {
 6                 zeroCount++;
 7             }
 8             while (zeroCount > K) {
 9                 if (A[start] == 0) {
10                     zeroCount--;
11                 }
12                 start++;
13             }
14             res = Math.max(res, end - start + 1);
15         }
16         return res;
17     }
18 }

 

Max Consecutive Ones III

原文:https://www.cnblogs.com/beiyeqingteng/p/12244468.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!