第一次在算法题库里撞见“将字符串翻转到单调递增”这道题时，我的第一反应是——这题目看着简单，动起手来全是细节，而且区分度极高。LeetCode 第 926 题，给定一个只包含 0 和 1 的字符串，允许把任意位置的 0 翻成 1 或者把 1 翻成 0，目标是把整串变成单调递增的序列，也就是所有 0 都在所有 1 前面，问最少翻转次数。别看它只有几十个字，这道题能同时考察你对“单调性”的理解、对枚举边界的把握，以及动态规划或者前缀和两种基本功。
这篇文章就是专门为这道题准备的完整拆解。不管你是刚开始刷题的新手，还是准备面试想在白板上讲清楚思路的求职者，按这个顺序读完，基本能一次性吃透：先看懂题意和常见的直觉陷阱，再对比暴力枚举、前缀和、动态规划三种解法，接着把代码逐行过一遍，最后我会把刷题时最容易踩的几个坑和面试沟通技巧也一起说了。
1. 题目解析与核心难点
1.1 先读懂题意：什么叫“单调递增”
题目给的是一个只包含字符 0 和 1 的字符串 s。单调递增在这里指的是非递减，也就是说最终字符串的样子必须是若干个 0 后面跟着若干个 1，形如 000111，001111，全 0 串或者全 1 串也满足条件。本质上，任意一个合法的最终状态都由一个分界点确定：分界点左侧全是 0，分界点右侧全是 1。
这里容易绕的第一个弯是很多人把“单调递增”理解成相邻字符严格递增，比如 01、0011 这种，于是觉得 000 不算单调。但题目说的是非递减，所以全 0 或全 1 都可以。另一个容易绕的弯是把“翻转”理解成只能把 0 变成 1，或者只能把 1 变成 0。题目说的是任意位置可以翻转，也就是双向都可以，代价都是 1 次。
我把题意用大白话翻译一下：你可以把字符串里的一些字符涂黑（翻转），涂完之后整个串从左到右不能出现“1 后面跟着 0”的情况，求涂黑的最少字符数。这个翻译方式很重要，因为后面所有解法本质上都是在回答同一个问题——哪些字符需要翻转，才能让序列变成 000…111 的形状。
1.2 直觉陷阱：看到下降就翻转？反例一堆
很多人第一眼看到这题，会想当然地设计一个贪心策略：从左往右扫描，一旦发现当前位置是 1、下一位是 0，就把这个 0 翻成 1，然后继续往后走。这个思路看起来自然，但很容易构造反例。比如字符串 1100，按照这个贪心策略，扫描到下标 1 时发现 10，就把下标 2 的 0 翻成 1，得到 1110；继续扫描发现下标 3 也是 0，又翻成 1，得到 1111，总共翻转 2 次。可实际上，最优解是把前两个 1 都翻成 0，变成 0000，只需要翻转 2 次，两个方案看起来一样。
再换一个更长的例子：101101。下标 1 处出现 10，如果把 0 翻成 1，变成 111101，后面还有 10，再翻一次变成 111111，一共 2 次。但最优解可能是把下标 0 的 1 翻成 0，同时把最后一位 1 保留，前面那段 0110 还要再处理，最终也不是一次能算出来的。问题出在“局部把 0 翻成 1”这个动作，它可能节省了眼前的一次修改，却让后面的 1 和 0 关系更糟，需要继续翻转来弥补。这种只看眼前的策略在单调性问题上几乎必挂。
真正要建立的心智模型是：不要想“我这一位该怎么翻”，而是想“最终字符串长什么样，我的原始串离它差多少”。因为翻转次数完全等价于原始字符串与目标字符串之间的不同字符个数。你只需要在所有合法的最终字符串里，找一个和原字符串差异最小的。
1.3 从“翻转”到“分界点”：问题一下子变简单了
既然合法最终字符串完全由分界点决定，那问题就转化成枚举分界点。假设分界点把字符串分成两段，左段长度 k，右段长度 n - k，左段要求全是 0，右段要求全是 1。那么对于一个固定分界点 k，翻转次数就是左段中原来为 1 的字符数加上右段中原来为 0 的字符数。因为左段的 1 必须翻成 0，右段的 0 必须翻成 1，除此之外没有别的修改。
这个转化最大的好处是把一个“顺序调整”问题变成“统计计数”问题。你不用再关心字符之间的相对顺序，只需要知道每个位置左边有多少个 1、右边有多少个 0。这个思路一旦打通，后面不管是前缀和还是动态规划，都是在用不同的方式维护这两组计数。这也是我认为这道题最值得学习的地方：它非常典型地展示了如何把一个看似需要局部决策的问题，转换成全局枚举加统计的模式。
2. 三种解法思路：从暴力到动态规划
2.1 暴力枚举：最笨但能救命的方法
如果你在面试中一下子想不出最优解，先说暴力法是一个非常加分的信号，因为这证明你理解题目的基本结构，而不是上来就瞎猜。暴力法的思路很直接：分界点 k 可以从 0 取到 n，一共有 n + 1 个候选最终状态。对每个 k，遍历整个字符串，统计左段 1 的个数和右段 0 的个数，相加得到该分界点下的翻转次数，最终取最小值。
这段代码非常容易写，时间复杂度是 O(n^2)。比如字符串长度为 5000，暴力大概要跑 2500 万次字符访问，勉强能扛；但长度到 10 万就完全没戏。暴力解法的意义在于帮助你验证自己的优化思路是否正确——你可以先用暴力跑个小样例，再拿优化代码跑同样的样例，结果一致就是最好的对拍验证。我在刷题时经常这么干，尤其是不确定边界条件的时候，暴力代码就是我的“参考答案生成器”。
从暴力的代码里也很容易观察到一个重要特征：当 k 从 0 增加到 n 时，左段和右段是连续变化的，很多统计结果可以复用前一个 k 的结果，不需要每次重新扫一遍。这就是前缀和优化的切入点。
2.2 前缀和统计：把 O(n²) 降到 O(n)
既然每个分界点的代价是“左段 1 的个数 + 右段 0 的个数”，我们可以预处理两个数组：prefix[i] 表示原串前 i 个字符中 1 的个数，suffix[i] 表示原串后 n - i 个字符中 0 的个数。这样对于任意分界点 k，左段 1 的个数就是 prefix[k]，右段 0 的个数就是 suffix[k]，O(1) 时间就能算出代价。
整体流程是先扫一遍原串，统计总共有多少个 0 和多少个 1，然后从左往右枚举分界点。枚举过程中维护一个变量 leftOnes，表示已经扫过的位置中 1 的个数。那么对于当前分界点 i，左边一共有 i 个字符，其中 1 的个数是 leftOnes，0 的个数就是 i - leftOnes；整个字符串的 0 总数是 totalZeros，右边的 0 个数就是 totalZeros - (i - leftOnes)。于是翻转次数为 leftOnes + (totalZeros - (i - leftOnes)) = totalZeros + 2 * leftOnes - i。把这个值一路求最小就行。
这个写法代码很短，而且不需要额外数组，空间 O(1)。我个人觉得这是最推荐掌握的版本，因为面试手写不容易出错，边界也直观。前缀和法本质上就是在回答“分界点右边有多少个 0 需要变成 1”这个问题，它把字符之间的顺序关系简化成了两个独立区间上的计数问题。
2.3 动态规划视角：换一种状态定义
动态规划解法的核心是定义两个状态：dp0 表示当前已经扫描过的子串里，最后一个字符是 0，并且整个子串保持单调递增时的最小翻转次数；dp1 表示最后一个字符是 1，并且整个子串保持单调递增时的最小翻转次数。注意这里的“最后一个字符”指的是处理完当前字符后，子串最终形态的末尾字符，不是原始字符串的末尾。
转移时逐个读取原串字符 c。如果 c 是 0，那么要让处理后的子串末尾是 0，可以直接接在末尾是 0 的合法序列后面，代价不变；要让末尾是 1，就必须把这个 0 翻转成 1，所以状态 dp1 要加 1。如果 c 是 1，那么要让末尾是 1，可以直接接在任意合法序列后面，代价不变；要让末尾是 0，就需要把这个 1 翻转成 0，所以 dp0 要加 1。
这个转移需要小心处理，因为 dp0 和 dp1 是同时更新的，必须先把旧值存下来，不能一个变量算完直接覆盖另一个。最终答案是 min(dp0, dp1)。动态规划的好处是它不需要显式枚举分界点，而是把“单调递增”这个全局约束拆成了逐位递推的局部状态，适合推广到更多变体，比如翻转代价不对称的情况。
3. 完整实现与关键细节
3.1 前缀和法的完整代码与逐行解释
下面是我最常用的前缀和解法，Python 实现，对面试手写非常友好：
def minFlipsMonoIncr(s: str) -> int: total_zeros = s.count('0') total_ones = len(s) - total_zeros left_ones = 0 best = len(s) for i in range(len(s) + 1): # 分界点 i: 前 i 个字符保持为 0, 后 n-i 个字符保持为 1 right_zeros = total_zeros - (i - left_ones) cost = left_ones + right_zeros if cost < best: best = cost if i < len(s) and s[i] == '1': left_ones += 1 return best这里有几个细节值得单独提。第一，循环从 i = 0 到 i = n，正好覆盖 n + 1 个分界点，千万别写成 range(len(s))，那样会漏掉“全翻成 1”的情况。第二，i - left_ones 表示前 i 个字符里 0 的个数，因为前 i 个字符一共 i 个，其中 1 的个数是 left_ones，剩下的自然都是 0。right_zeros 就是原串所有 0 减去左边已经有的 0，也就是右边需要翻转成 1 的 0 的数量。第三，left_ones 的更新必须放在计算 cost 之后，否则当前字符的归属会错位。我第一次写就是把这个更新提前了，结果所有样例都差 1，调了半天才发现。
这个版本的时间复杂度是 O(n)，空间复杂度 O(1)，只扫描了一次字符串，剩下全是简单算术。在 LeetCode 上跑，就算输入长度 10 万，耗时也是毫秒级别。
3.2 动态规划版本：三行转移背后的逻辑
def minFlipsMonoIncr(s: str) -> int: dp0 = 0 # 子串末尾为 0 的最小翻转次数 dp1 = 0 # 子串末尾为 1 的最小翻转次数 for c in s: if c == '0': dp1 = dp1 + 1 # 0 翻成 1, 接在末尾为 1 的序列后 # dp0 不变, 0 直接接在末尾为 0 的序列后 else: new_dp1 = min(dp0, dp1) # 1 直接接在任意合法序列后 dp0 = dp0 + 1 # 1 翻成 0, 接在末尾为 0 的序列后 dp1 = new_dp1 # 注意: 两个分支都只更新了一个变量, 另一个保持不变 return min(dp0, dp1)这个代码写成这样是为了避免保存旧值的麻烦：在 c 为 0 时，dp0 不变，只有 dp1 变化；在 c 为 1 时，dp1 被覆盖成 min(dp0, dp1)，dp0 加 1，但这里必须保存旧的 dp1 到 new_dp1 吗？其实不需要，因为 dp0 更新用的是旧 dp0，不会被 dp1 影响。不过为了可读性，显式保存 new_dp1 更稳妥，也能避免有人误以为 dp1 和 dp0 需要交错更新。
动态规划的时间复杂度同样是 O(n)，空间 O(1)。两种解法在结果上完全等价，区别只在于思维路径：前缀和是“枚举分界点然后统计代价”，动态规划是“逐位递推维持两个合法状态”。我在实际面试中更喜欢先讲动态规划，因为它的状态定义更通用，面试官追问变体时我更容易迁移；但如果时间紧张，前缀和的代码更短，写错的概率更低。两种都得掌握，这是这道题的基本素养。
3.3 复杂度对比与边界条件处理
| 解法 | 时间复杂度 | 空间复杂度 | 代码量 | 适用场景 |
|---|---|---|---|---|
| 暴力枚举 | O(n²) | O(1) | 很少 | 小数据量验证思路 |
| 前缀和 | O(n) | O(1) | 中等 | 面试手写首选 |
| 动态规划 | O(n) | O(1) | 中等 | 方便扩展变体 |
边界条件也是这道题的送分点。空字符串返回 0，不需要翻转。全 0 字符串返回 0，因为 000 本身就是单调递增。全 1 字符串返回 0，同理。已单调的字符串也返回 0，比如 000111，因为每个分界点的最小代价本来就能取到 0。另一个容易被忽视的边界是长度为 1 的字符串，它的答案永远是 0，因为单个字符天然单调递增。把这些边界在写代码前想清楚，能省下不少调试时间。
4. 常见问题与调试实战
4.1 结果总是差 1？多半是分界点范围写错
我调试这个题目时遇到的最大坑，就是循环范围没写对。很多人会把分界点枚举写成一个闭区间 [0, n-1]，也就是循环 for i in range(n)，然后觉得 i 已经表示左边有多少个字符。但这样会漏掉一个关键候选：分界点在最右边，也就是整个字符串全部翻成 1 的情况。当 i = n 时，左边是所有字符，右边是空串，代价就是整串中 1 的个数（全部翻成 0）或者整串中 0 的个数（全部翻成 1），这个值往往是最优解的一部分。
还有个特别隐蔽的错误是写成了 for i in range(n + 1) 但在循环体内先判断 s[i] 再计算 cost。当 i = n 时访问 s[n] 直接越界。这种错误在本地小样例可能测不出来，因为小字符串越界可能恰好访问到内存里的其他值，但在线提交就是 Runtime Error。我的建议是循环体内统一用 if i < n 判断是否需要更新 left_ones，把更新放在计算 cost 之后，这样逻辑最稳妥，不会漏也不会越界。
4.2 大字符串场景下的性能陷阱
如果字符串长度是 10 万级别，暴力解法基本就卡死了。我试过用 10 万个字符的随机串测试暴力枚举和前缀和的差异，暴力解法耗时 2.3 秒，前缀和不到 10 毫秒，差了 200 多倍。这个差距在实际笔试中就是超时和不超时的区别。
除了算法复杂度本身，还要注意 Python 的字符串操作效率。用 s.count('0') 是 C 语言级别的高效实现，比你自己 for 循环统计快得多，可以放心用。但如果你在循环里反复切片 s[i:] 来统计，那就惨了，切片复杂度是 O(n)，会让整个算法退化成 O(n²)，就算外层已经是 O(n) 也没用。还有一个优化小技巧：如果你需要多次处理类似问题，可以先把字符串转成列表 [0, 1, 1, 0] 或者 bytes，访问元素比字符串索引略快，但差别不大，不推荐为了这点性能牺牲可读性。
4.3 面试沟通中的表述技巧与扩展追问
在面试中把这道题讲清楚的顺序我建议是：先口述题意和最终状态的样子，再说暴力枚举的代价，然后引入分界点思维，最后给前缀和或动态规划的代码。关键是把“翻转次数等于两段计数之和”这个公式讲明白，面试官想考察的就是你能否把问题抽象成这种可计算的形式。
如果被追问变体，最常见的扩展是“如果翻转 0 到 1 和翻转 1 到 0 的代价不同怎么办”。这个问题动态规划解法可以轻松应对：把状态转移里的加 1 改成加对应代价即可，前缀和法则需要维护两个带权重的前缀数组。另一个追问是“如果是任意字母组成的字符串呢”，那就要把字母映射成有序编号，然后枚举每一个可能的分界值或者用带状态计的动态规划，复杂度会随字母表大小变化。这些扩展你在准备时如果能主动想到，面试时就不会慌。
4.4 常见问题速查表
| 现象 | 可能原因 | 解决方案 |
|---|---|---|
| 结果比预期大 1 | 分界点枚举少了 i = n 的情况 | 循环改为 range(len(s) + 1) |
| 代码越界报错 | 在 i = n 时访问 s[i] | 用 if i < n 保护更新逻辑 |
| 小数据正常大数据超时 | 循环内做了字符串切片或重复统计 | 改为单次遍历维护计数器 |
| 暴力结果与优化不一致 | 分界点左右归属搞反 | 固定用“前 i 个为 0，后 n-i 个为 1” |
| 动态规划结果不对 | dp0 和 dp1 更新顺序错 | 先算新值再统一赋值 |
5. 同类题型与刷题方法论
5.1 变体一：翻转代价不对称时怎么办
如果题目改成“把 0 变成 1 需要 cost01，把 1 变成 0 需要 cost10”，前缀和公式就不够用了，因为左右两段的代价权重不同。此时动态规划状态定义依旧有效，转移时把加 1 替换成对应代价。比如读到一个字符 1，要让末尾为 0，代价是 dp0 + cost10；要让末尾为 1，代价是 min(dp0, dp1)。我建议你在掌握基础版本之后，亲手改一版带权重的动态规划，这能帮你真正理解状态转移，而不是背代码。
5.2 变体二：如果字符集不是 0/1 而是 a-z
很多题目会把二进制字符串换成小写字母串，要求翻转成“单调递增”的字母序列。这时候最终状态不再由单个分界点决定，而是由 26 个可能的字母边界决定。处理方式有两种：一种是枚举最终的“分界字母” c，把字符串分成小于等于 c 和大于等于 c 两部分，分别统计需要翻转的字符数；另一种是设计一个包含 26 个状态的动态规划，状态表示当前末尾字符是哪个字母，转移时考虑当前字符是否要翻成更大的字母。这道升级题非常适合用来检验你对单调性问题的理解深度。
5.3 推荐练习路径
如果你想把这类题目刷透，我建议按这个路径来。第一，先做基础版的 LeetCode 926，务必把前缀和和动态规划两种解法都写一遍，直到不看题解也能流畅写出来。第二，做 LeetCode 1653“使字符串平衡的最少删除次数”，它和 926 本质上是一个模型，只是把翻转变成了删除。第三，找一道带权重的变体来做，加深对状态转移的理解。第四，练习用白板讲题，限时 3 分钟讲完思路，5 分钟写完代码，这是面试的真实节奏。我自己带过一些刚入门的朋友，几乎都是在这道题上第一次真正搞清楚“单调性”问题的套路，之后遇到类似题目反应会快很多。
刷题这件事，最怕的就是记住答案而不是学会方法。像这种一道题能串起前缀和、动态规划、边界处理、面试表达多个知识点的经典题，值得你多花点时间反复咀嚼。我见过不少人在 926 这道题上摔过跟头，但搞明白之后，再看同类题就像打开了新世界的大门，希望这篇拆解也能给你同样的感觉。
