一、题目描述给定一个二进制数组nums和一个整数k假设最多可以翻转k个0则返回执行操作后数组中连续 1 的最大个数。示例 1输入nums [1,1,1,0,0,0,1,1,1,1,0], K 2 输出6 解释[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1最长的子数组长度为 6。示例 2输入nums [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K 3 输出10 解释[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1最长的子数组长度为 10。提示1 nums.length 10^5nums[i]不是 0 就是 10 k nums.length二、题目本质分析这道题表面上是在问翻转 k 个 0 后能得到多长的连续 1但换个角度理解等价于在一个二进制数组中找到一个最长的子数组使得子数组中 0 的个数不超过 k。这个转化非常关键因为翻转 k 个 0实际上就是允许窗口内出现最多 k 个 0。一旦想清楚这一点问题就变成了求满足条件的最长子数组长度而这类问题有两个经典解法滑动窗口双指针—— 最优解O(n)动态规划—— 辅助理解O(n·k)三、法一滑动窗口3.1 核心思路维护一个窗口[left, right]保证窗口内0的个数不超过k。右指针right扩张每次把nums[right]加入窗口如果是 0则zeroCount。当窗口内 0 的个数超过 k 时说明窗口不合法需要左指针left收缩直到zeroCount k。收缩时如果移出的是 0则zeroCount--。每次窗口合法时用right - left 1更新答案。3.2 图示理解以示例 1 为例nums [1,1,1,0,0,0,1,1,1,1,0], k 2初始: left0, right0, zeroCount0 右扩: [1] zeroCount0, 合法, ans1 右扩: [1,1] zeroCount0, 合法, ans2 右扩: [1,1,1] zeroCount0, 合法, ans3 右扩: [1,1,1,0] zeroCount1, 合法, ans4 右扩: [1,1,1,0,0] zeroCount2, 合法, ans5 右扩: [1,1,1,0,0,0] zeroCount3, 不合法 收缩: [1,1,0,0,0] 移出1 zeroCount3, 仍不合法 收缩: [1,0,0,0] 移出1 zeroCount3, 仍不合法 收缩: [0,0,0] 移出1 zeroCount3, 仍不合法 收缩: [0,0,0] 移出0 zeroCount2, 合法 右扩: [0,0,0,1] zeroCount2, 合法, ans4 右扩: [0,0,0,1,1] zeroCount2, 合法, ans5 ...以此类推 最终最长窗口: [0,0,1,1,1,1,1,1] (长度 6)3.3 代码实现Cclass Solution { public: int longestOnes(vectorint nums, int k) { int left 0, right 0; int zeroCount 0; // 当前窗口内 0 的个数 int maxLen 0; while (right nums.size()) { // 右指针元素进入窗口 if (nums[right] 0) { zeroCount; } // 如果窗口内 0 的个数超过 k左指针收缩 while (zeroCount k) { if (nums[left] 0) { zeroCount--; } left; } // 更新最大长度 maxLen max(maxLen, right - left 1); right; } return maxLen; } };3.4 复杂度分析时间复杂度O(n)。left和right各自最多向右移动 n 次总移动次数不超过 2n。空间复杂度O(1)。只使用常数个变量。四、法二动态规划会超出内存限制4.1 为什么可以用 DP滑动窗口是空间上的贪心而 DP 是另一种思路从每个位置出发思考以该位置结尾的最长合法子数组能有多长。4.2 状态定义定义dp[i][j]表示以nums[i]为结尾且恰好使用了j次翻转机会时能得到的最长连续 1 的长度。这里的恰好使用 j 次是指最多可以使用 j 次因为翻不翻是灵活的但为了状态统一我们约定j表示预算遇到 0 就消耗一次。4.3 状态转移方程分两种情况讨论情况 1nums[i] 1不需要消耗翻转次数直接延长前一个状态即可dp[i][j] dp[i-1][j] 1情况 2nums[i] 0必须消耗一次翻转机会如果j 0还有翻转次数则dp[i][j] dp[i-1][j-1] 1如果j 0没有翻转次数了遇到 0 只能断掉dp[i][j] 04.4 为什么以 i 结尾很重要因为题目要求的是连续子数组。定义状态时明确以nums[i]结尾转移时才能强制连续。如果定义成dp[i][j]为前 i 个元素中的最长连续 1就无法正确转移因为子数组可能从前面的某个位置开始不一定包含nums[i]。4.5 初始化dp数组大小为(n1) × (k1)全部初始化为 0。dp[0][*] 0表示还没有元素长度为 0。遍历时i从 1 到 nj从 0 到 k。4.6 代码实现Cclass Solution { public: int longestOnes(vectorint nums, int k) { int n nums.size(); // dp[i][j] 表示以 i 结尾用了 j 次翻转的最大长度 vectorvectorint dp(n 1, vectorint(k 1, 0)); int ans 0; for (int i 1; i n; i) { for (int j 0; j k; j) { if (nums[i - 1] 1) { dp[i][j] dp[i - 1][j] 1; } else { // nums[i-1] 0 if (j 0) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] 0; // 没有翻转次数了遇到0只能断 } } ans max(ans, dp[i][j]); } } return ans; } };4.7 举例演示以nums [1,1,1,0,0,0,1,1,1,1,0], k 2为例展示部分 DP 过程inums[i-1]j0j1j2111112122231333400445001560002711138122491335101446110055最后答案取所有dp[i][j]的最大值即6。4.8 复杂度分析时间复杂度O(n·k)。双重循环外层 n内层 k。空间复杂度O(n·k)。二维数组