题目链接:1004. 最大连续1的个数 III。
题目要求,给定一个数组,这个数组里面只有0或1,然后计算有多少个连续的1的最大长度,同时给了一个条件就是,可以把k个0变成1,然后来计算长度。
暴力解法:枚举每一个子数组,记录连续为1的长度,同时用一个计数器cut来统计0的个数。
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int sum = INT_MIN;for(int i = 0;i < n;i++){int cut = 0;int sum1 = 0;for(int j = i;j < n;j++){if(nums[j] == 0){cut++;}if(cut == k+1){break;}sum1++;}sum = sum1 > sum ? sum1 : sum;}return sum;}
};
但是暴力解法会超时!!!
在暴力解法前提下进行对代码的优化:
- 通过定义两个指针来控制,left固定在第一个位置,right进行移动,定义cut当计数器
- 如果right对应值为1,则无视,直接++
- 如果right对应值为0,则cut++,right也++
- 判断,如果cut > k,则开始移动left
- 如果left对应值为1,无视,直接++
- 如果对应值为0,则cut--,left也++
- 判断完就进行更新长度
为什么判断cut > k后要进行移动left,而right不动,因为left到right之间0的个数已经超过k,此时right在回到left位置重新进行检测长度,没有必要,因为重新检测的长度肯定比之前长度短,所以只需要更新left,更新到cut=k的位置,然后再进行移动right。
这样同向双指针操作叫做滑动窗口。
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0,right = 0,cut = 0;int n = nums.size();int ret = 0;while(left<n && right < n){if(nums[right] == 0) cut++;while(cut > k){if(nums[left] == 0) cut--;left++;}ret = max(ret , right - left + 1);right++;}return ret;}
};