Skip to content

Latest commit

 

History

History
 
 

1004.Max-Consecutive-Ones-III

1004.Max-Consecutive-Ones-III

解法1:DP

令dp[i][k]表示截止到第i个元素位置,我们行使了k次翻转权利的话,最长的连续1区间的长度。突破口就是第i个元素我们是否进行翻转:

  1. 如果A[i]==1,那么我们不需要翻转,即dp[i][k] = dp[i-1][k]+1
  2. 如果A[i]==0,那么我们需要翻转,即dp[i][k] = dp[i-1][k-1]+1,注意k不能超过题目规定的行使反转权利的上限K。 答案就是dp[x][K]中的最大值。

以上方法的两层循环的时间复杂度是o(NK),显然会超时。

解法2:双指针

对于任何求subarray的问题,我们通常的做法就是固定左边界,探索右边界。假设我们固定左边界是i,那么要使右边界j最远,需要满足[i,j]最多有K个0。

此时我们考虑左边界是i+1的情况。如果A[i+1]==1,那么此时[i+1,j]内的需要翻转元素的个数count依然是K,然而右边界j依然不能往右突破。我们只有不停地移动i,直到A[i]==0的时候,意味着第i个元素的不被允许翻转,所以区间内的翻转次数count-=1,因此右边界就又可以移动,直到找到下一个A[j]==0为止(此时count再次变为K)。

所以两个指针都只会朝一个方向移动。这是快慢类型的双指针,时间复杂度就是o(N).