1004. (最大连续1的个数) Max Consecutive Ones III

问题理解

给定一个二进制数组 nums 和整数 k，最多可以将 k 个 0 翻转为 1，求翻转后最长的连续 1 子数组的长度。等价于：找一个最长子数组，其中 0 的个数 ≤ k。

思路

使用 滑动窗口（双指针） 技术：

• 维护窗口 [i, j)（左闭右开），其中 i 是左边界，j 是右边界（指向下一个待处理元素）。
• 用变量 flips 表示当前还能翻转多少个 0（初始为 k）。
• 右指针 j 不断向右扩展：
  • 遇到 1：直接纳入窗口；
  • 遇到 0：若还有翻转次数（flips > 0），则消耗一次；否则停止扩展。
• 左指针 i 每次右移时：
  • 如果刚离开窗口的元素是 0（即 nums[i-1] == 0），说明之前消耗了一次翻转，现在应归还一次翻转机会（flips++）。
• 记录所有合法窗口的最大长度 j - i。

⚠️ 注意：窗口定义为 [i, j)，因此长度是 j - i，不是 j - i + 1。

trick

• 避免越界：在访问 nums[i-1] 前必须判断 i != 0。
• 状态复用：j 指针永不回退，保证整体时间复杂度为 O(n)。
• 翻转次数管理：通过“借”和“还”机制维护 flips，确保其始终反映当前窗口的剩余翻转能力。
• 左闭右开窗口：简化边界处理，j 始终是第一个未包含的元素。

Code

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int ans = 0;int i = 0, j = 0, next_1 = 0;int n = nums.size();int flips = k;for(int i = 0; i < n; i++){if(j == n) break;if(i != 0 && nums[i - 1] == 0){flips++;}while (j < n) {if (nums[j] == 0) {if (flips == 0) break; // 不能再翻了flips--;}j++; // j 是下一个要处理的位置，当前 [i, j-1] 是合法窗口}ans = max(ans, j - i);}return ans;}
};