LeetCode 1004 最大连续 1 的个数 III基于滑动窗口的一次遍历解法含换皮题模型总结【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南基于题解仓库中的文档 problems/1004.max-consecutive-ones-iii.md完整讲解「最大连续 1 的个数 III」这道经典的滑动窗口题从题目约束出发给出窗口进出时「零计数」的维护规则解释该算法为什么能把暴力枚举的 O(n²) 降到 O(n)并给出两个可直接运行的 Python3 实现。读完后你不仅能独立解出本题还能识别仓库中反复出现的「最长连续 1 模型」快速应对它的各类换皮变体如替换字符类题目。题目描述给定一个由若干 0 和 1 组成的数组 A最多可以将 K 个值从 0 变成 1。返回仅包含 1 的最长连续子数组的长度。示例 1输入A [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输入A [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 A.length 200000 K A.lengthA[i]为 0 或 1约束中有两个值得注意的边界K可以为 0退化为寻找最长的连续 1 段K最大可以等于数组长度整个数组都能被翻转答案就是 n。这两个边界在验证实现正确性时值得各测一组。核心思路用 K 直接充当「可用翻转次数」如果题目没有「最多可以将 K 个值从 0 变成 1」这个条件那么这是一道常规的滑动窗口模板题。加上这个条件后对问题有什么影响关键观察是我们不需要真正记录窗口内有几个 0只需要跟踪「翻转预算 K 还剩多少」。具体规则如下加入窗口右指针右移时如果是 1什么都不用做如果是 0将 K 减 1相当于花掉一次翻转机会。相应地移除窗口左指针右移时如果是 1什么都不做如果是 0说明加进来的时候它是 0、当时 K 减去了 1现在把它移出窗口就把这 1 加回去。如果 K 减少到负数意味着窗口内的 0 超过了翻转预算则收缩窗口左指针右移直到 K 恢复为非负。在整个过程中不断用满足条件的窗口大小更新答案即可。这里用A[j] 0这种布尔表达式直接参与加减法是 Python 的常见技巧布尔值是整数的子类True等价于 1、False等价于 0因此K - A[j] 0等价于若 A[j] 是 0 则 K 减 1。为什么这种思路可行从暴力枚举到双指针原文档给出了分两步的严格论证这里完整继承第一步滑动窗口把窗口内的计数从 O(w) 降到 O(1)。最暴力的解法是枚举所有子数组——O(n²) 的枚举量然后逐个判断子数组是否满足「最多将 k 个 0 变成 1使子数组全部为 1」满足则更新答案。滑动窗口的优化点在于假设已经算出子数组 A[2:3] 有 1 个 0那么继续判断 A[2:4] 时只需要处理新增的 A[4]并复用 A[2:3] 的计数信息。滑动窗口专门针对每次只在端点变化、中间都不变的场景省去了中间部分的重复计算将窗口内的计数信息从 O(w) 降低到 O(1)w 为窗口大小。第二步双指针把 O(n²) 的子数组枚举降到 O(n)。实际上也没有必要用两层循环枚举所有子数组O(n) 的时间就可以枚举所有合法子数组。换个角度思考所有子数组就是以索引 0 为右端点的所有子数组加上以索引 1 为右端点的所有子数组加上以索引 2 为右端点的所有子数组...加上以索引 n - 1 为右端点的所有子数组n 为数组长度于是使用双指针技巧右指针模拟右端点左指针模拟左端点。如果以索引 i 为右端点的子数组中 0 的个数不大于 k那么左指针 l 没必要右移——因为当前右指针 r 和所有满足 l i r 的索引 i 的组合中0 的个数都不会大于 k而子数组反而更短了不可能是答案。因此直接右移右指针这是算法的关键。通过这两步时间复杂度从 O(n²) 降低到 O(n)。代码实现Python3解法一标准滑动窗口模板。显式维护答案ans用while循环收缩窗口直到 K 恢复非负class Solution: def longestOnes(self, A: List[int], K: int) - int: i 0 # 左指针慢指针 ans 0 for j in range(len(A)): K - A[j] 0 # 窗口加入一个 0 时消耗一次翻转机会 while K 0: # 窗口内 0 的数量超过预算收缩窗口 K A[i] 0 # 窗口移出一个 0 时归还一次翻转机会 i 1 ans max(ans, j - i 1) # 用合法窗口更新答案 return ans解法二更简洁的写法。利用右指针单调右移、答案单调不减的性质每次K 0时左指针只需右移恰好一位即可恢复合法因为窗口内最多只有预算 1个 0所以while可以退化为if又因为最终答案一定在右指针走完整个数组时取得连ans变量都可以省去class Solution: def longestOnes(self, A: List[int], K: int) - int: i 0 for j in range(len(A)): K - 1 - A[j] if K 0: K 1 - A[i] i 1 return j - i 1注意K - 1 - A[j]与K - A[j] 0等价当A[j]是 0 时1 - A[j]为 1是 1 时为 0。复杂度分析令 n 为数组长度。时间复杂度O(n)。右指针 j 从 0 走到 n-1左指针 i 最多跟着右移 n 次两个指针各自只做单向、有界的移动总步数是 O(2n) 即 O(n)。空间复杂度O(1)。只用了常数额外空间K 被原地复用未保留原始值。延伸最长连续 1 模型及其换皮题这道题不是孤立的仓库中它被反复引用为一个「模型」。字节跳动面试的换皮题。仓库文章 selected/byte-dance-algo-ex.md 记录了字节跳动的一道面试题给定仅含 a、b 的字符串 s最多转换 m 次a 变 b 或 b 变 a求最长连续相同字符的长度。原文档明确指出这道题其实就是……1004 的换皮题。做法是把 a 看作 0、b 看作 1或反过来分别跑一遍 1004 的解法取较大值抽象之后代码与上面完全同构。该文中还给出了一个直观的形象化解释将 1 看成墙、0 看成洞目标是用不超过 m 次的补洞使连续的墙最长每次碰到洞不加选择地修补补超了就收缩窗口窗口的最大值即答案。字符替换的换皮题。仓库题解 problems/424.longest-repeating-character-replacement.md424. 替换后的最长重复字符同样被标注为 1004 的换皮题并提出了本系列的命名——「最长连续 1 模型」核心算法是维护一个可变窗口窗口内的不重复字符本题即 0小于等于 k最终返回最大窗口的大小。424 的差异在于目标字母有 26 种可能而非 1 种一种朴素做法是枚举 26 种目标字母各跑一遍窗口O(26·n)另一种做法是用长度为 26 的频数数组做空间换时间当窗口大小超过最大频率 k时收缩窗口达到 O(n)。与滑动窗口专题的关系。仓库的专题文章 thinkings/slide-window.md 将 1004 列入了「题目列表有题解」其通用可变窗口流程是l、r 都初始化为 0r 指针移动一步判断窗口是否满足条件——满足则更新最优解并尝试移动 l 缩小窗口不满足则继续。1004 恰好属于该专题分类中的窗口大小不固定求解最大的满足条件的窗口这一类型其判定条件就是K 0时收缩可对照该专题的伪代码模板理解整体框架。小结1004 的价值在于它把一个带「翻转预算」的约束压缩成了对预算变量的原地加减窗口进 0 则预算减一、窗口出 0 则预算加一预算为负即收缩窗口。掌握这套「最长连续 1 模型」后面对 424 这类字符替换题乃至字节跳动面试题中的字符串转换题都可以直接套用同一框架只需调整什么算 0的定义以及必要时枚举目标字符。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/18 21:40:39 · 阅读 1.2k LeetCode 1004 最大连续 1 的个数 III：基于滑动窗口的一次遍历解法（含换皮题模型总结）
LeetCode 1004 最大连续 1 的个数 III基于滑动窗口的一次遍历解法含换皮题模型总结【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南基于题解仓库中的文档 problems/1004.max-consecutive-ones-iii.md完整讲解「最大连续 1 的个数 III」这道经典的滑动窗口题从题目约束出发给出窗口进出时「零计数」的维护规则解释该算法为什么能把暴力枚举的 O(n²) 降到 O(n)并给出两个可直接运行的 Python3 实现。读完后你不仅能独立解出本题还能识别仓库中反复出现的「最长连续 1 模型」快速应对它的各类换皮变体如替换字符类题目。题目描述给定一个由若干 0 和 1 组成的数组 A最多可以将 K 个值从 0 变成 1。返回仅包含 1 的最长连续子数组的长度。示例 1输入A [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输入A [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 A.length 200000 K A.lengthA[i]为 0 或 1约束中有两个值得注意的边界K可以为 0退化为寻找最长的连续 1 段K最大可以等于数组长度整个数组都能被翻转答案就是 n。这两个边界在验证实现正确性时值得各测一组。核心思路用 K 直接充当「可用翻转次数」如果题目没有「最多可以将 K 个值从 0 变成 1」这个条件那么这是一道常规的滑动窗口模板题。加上这个条件后对问题有什么影响关键观察是我们不需要真正记录窗口内有几个 0只需要跟踪「翻转预算 K 还剩多少」。具体规则如下加入窗口右指针右移时如果是 1什么都不用做如果是 0将 K 减 1相当于花掉一次翻转机会。相应地移除窗口左指针右移时如果是 1什么都不做如果是 0说明加进来的时候它是 0、当时 K 减去了 1现在把它移出窗口就把这 1 加回去。如果 K 减少到负数意味着窗口内的 0 超过了翻转预算则收缩窗口左指针右移直到 K 恢复为非负。在整个过程中不断用满足条件的窗口大小更新答案即可。这里用A[j] 0这种布尔表达式直接参与加减法是 Python 的常见技巧布尔值是整数的子类True等价于 1、False等价于 0因此K - A[j] 0等价于若 A[j] 是 0 则 K 减 1。为什么这种思路可行从暴力枚举到双指针原文档给出了分两步的严格论证这里完整继承第一步滑动窗口把窗口内的计数从 O(w) 降到 O(1)。最暴力的解法是枚举所有子数组——O(n²) 的枚举量然后逐个判断子数组是否满足「最多将 k 个 0 变成 1使子数组全部为 1」满足则更新答案。滑动窗口的优化点在于假设已经算出子数组 A[2:3] 有 1 个 0那么继续判断 A[2:4] 时只需要处理新增的 A[4]并复用 A[2:3] 的计数信息。滑动窗口专门针对每次只在端点变化、中间都不变的场景省去了中间部分的重复计算将窗口内的计数信息从 O(w) 降低到 O(1)w 为窗口大小。第二步双指针把 O(n²) 的子数组枚举降到 O(n)。实际上也没有必要用两层循环枚举所有子数组O(n) 的时间就可以枚举所有合法子数组。换个角度思考所有子数组就是以索引 0 为右端点的所有子数组加上以索引 1 为右端点的所有子数组加上以索引 2 为右端点的所有子数组...加上以索引 n - 1 为右端点的所有子数组n 为数组长度于是使用双指针技巧右指针模拟右端点左指针模拟左端点。如果以索引 i 为右端点的子数组中 0 的个数不大于 k那么左指针 l 没必要右移——因为当前右指针 r 和所有满足 l i r 的索引 i 的组合中0 的个数都不会大于 k而子数组反而更短了不可能是答案。因此直接右移右指针这是算法的关键。通过这两步时间复杂度从 O(n²) 降低到 O(n)。代码实现Python3解法一标准滑动窗口模板。显式维护答案ans用while循环收缩窗口直到 K 恢复非负class Solution: def longestOnes(self, A: List[int], K: int) - int: i 0 # 左指针慢指针 ans 0 for j in range(len(A)): K - A[j] 0 # 窗口加入一个 0 时消耗一次翻转机会 while K 0: # 窗口内 0 的数量超过预算收缩窗口 K A[i] 0 # 窗口移出一个 0 时归还一次翻转机会 i 1 ans max(ans, j - i 1) # 用合法窗口更新答案 return ans解法二更简洁的写法。利用右指针单调右移、答案单调不减的性质每次K 0时左指针只需右移恰好一位即可恢复合法因为窗口内最多只有预算 1个 0所以while可以退化为if又因为最终答案一定在右指针走完整个数组时取得连ans变量都可以省去class Solution: def longestOnes(self, A: List[int], K: int) - int: i 0 for j in range(len(A)): K - 1 - A[j] if K 0: K 1 - A[i] i 1 return j - i 1注意K - 1 - A[j]与K - A[j] 0等价当A[j]是 0 时1 - A[j]为 1是 1 时为 0。复杂度分析令 n 为数组长度。时间复杂度O(n)。右指针 j 从 0 走到 n-1左指针 i 最多跟着右移 n 次两个指针各自只做单向、有界的移动总步数是 O(2n) 即 O(n)。空间复杂度O(1)。只用了常数额外空间K 被原地复用未保留原始值。延伸最长连续 1 模型及其换皮题这道题不是孤立的仓库中它被反复引用为一个「模型」。字节跳动面试的换皮题。仓库文章 selected/byte-dance-algo-ex.md 记录了字节跳动的一道面试题给定仅含 a、b 的字符串 s最多转换 m 次a 变 b 或 b 变 a求最长连续相同字符的长度。原文档明确指出这道题其实就是……1004 的换皮题。做法是把 a 看作 0、b 看作 1或反过来分别跑一遍 1004 的解法取较大值抽象之后代码与上面完全同构。该文中还给出了一个直观的形象化解释将 1 看成墙、0 看成洞目标是用不超过 m 次的补洞使连续的墙最长每次碰到洞不加选择地修补补超了就收缩窗口窗口的最大值即答案。字符替换的换皮题。仓库题解 problems/424.longest-repeating-character-replacement.md424. 替换后的最长重复字符同样被标注为 1004 的换皮题并提出了本系列的命名——「最长连续 1 模型」核心算法是维护一个可变窗口窗口内的不重复字符本题即 0小于等于 k最终返回最大窗口的大小。424 的差异在于目标字母有 26 种可能而非 1 种一种朴素做法是枚举 26 种目标字母各跑一遍窗口O(26·n)另一种做法是用长度为 26 的频数数组做空间换时间当窗口大小超过最大频率 k时收缩窗口达到 O(n)。与滑动窗口专题的关系。仓库的专题文章 thinkings/slide-window.md 将 1004 列入了「题目列表有题解」其通用可变窗口流程是l、r 都初始化为 0r 指针移动一步判断窗口是否满足条件——满足则更新最优解并尝试移动 l 缩小窗口不满足则继续。1004 恰好属于该专题分类中的窗口大小不固定求解最大的满足条件的窗口这一类型其判定条件就是K 0时收缩可对照该专题的伪代码模板理解整体框架。小结1004 的价值在于它把一个带「翻转预算」的约束压缩成了对预算变量的原地加减窗口进 0 则预算减一、窗口出 0 则预算加一预算为负即收缩窗口。掌握这套「最长连续 1 模型」后面对 424 这类字符替换题乃至字节跳动面试题中的字符串转换题都可以直接套用同一框架只需调整什么算 0的定义以及必要时枚举目标字符。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考