LeetCode 926. 将字符串翻转到单调递增
目录
题目描述
题意分析
给一个只含
0和1的字符串，一次操作可以把某一位从0改成1或从1改成0。要让整个串变成单调递增，问最少需要多少次操作。这里的「单调递增」按位比较，也就是不允许出现某个
1排在某个0前面。把它展开写，合法串一定形如000...0111...1——前面一段全 0、后面一段全 1，两段都允许为空。全 0 串和全 1 串都是合法的。于是题意可以完全等价地重述为：在串中选一个分界位置，把分界前的所有
1翻成0、分界后的所有0翻成1，使总翻转数最小。分界点有n + 1个候选（含两端），暴力枚举每个分界点再统计两侧代价是 $O(n^2)$。约束里串长最多 $10^5$，$O(n^2)$ 是 $10^{10}$ 次操作，必然超时。所以需要一个线性做法。
边界：串已经单调递增时答案是 0；全 0 或全 1 时答案也是 0；
"10"需要 1 次（把1改成0，或把0改成1，两种方案代价相同）。
解法：DP（结尾为 0/1 的最少翻转）
核心思路
顺着「枚举分界点」的思路优化，可以用前缀和：预处理前缀 1 的个数与后缀 0 的个数，每个分界点 $O(1)$ 求代价，总共 $O(n)$。这是完全正确的解法。但它需要额外的数组，而且「分界点」这个概念在更复杂的变体（比如允许出现第三段）里不好推广。
换成 DP 的视角更本质，也更容易在面试中一路推到底。核心观察是：判断一个前缀能否继续保持单调，只需要知道它最后一位是 0 还是 1。前面的具体形状无关紧要——最后一位是 0，说明整段都是 0，后面还能接 0 或 1；最后一位是 1，说明已经进入 1 的区域，后面只能接 1。这就把「历史」压缩成了一个二值状态。
状态定义：扫描到第
i位（含）时，dp0表示「把前i位改造成合法单调串、且第i位为 0」的最少翻转次数；dp1表示「改造成合法单调串、且第i位为 1」的最少翻转次数。转移，设当前字符为
c：第
i位最终为 0，则前面所有位也必须是 0（否则会出现 1 在 0 前面），所以只能从上一位的dp0转移而来。若c == '1'需要翻转一次，否则不翻。即 $dp0' = dp0 + [c = 1]$。第
i位最终为 1，则前面既可以是全 0（从dp0来），也可以是已经进入 1 区域（从dp1来），取两者较小值。若c == '0'需要翻转一次。即 $dp1' = \min(dp0, dp1) + [c = 0]$。初始条件：
dp0 = dp1 = 0，表示空前缀，两种「结尾状态」都不需要任何代价。空串既可以看作以 0 结尾也可以看作以 1 结尾，这个初值让第一个字符的转移自然成立。不变量：每处理完一个字符，
dp0与dp1恒等于「把已扫过的前缀改造成合法单调串，且末位分别为 0 / 1」的最小代价。这两个值涵盖了所有可能的合法形态，因此最终答案是 $\min(dp0, dp1)$。转移只依赖上一位的两个值，所以用两个标量滚动即可，空间 $O(1)$。但要注意更新顺序：新的
dp1用到旧的dp0，而新的dp0又要覆盖旧的dp0，所以必须先把新dp1算进临时变量，再更新dp0，最后才把临时值写回dp1。
解题步骤
- 初始化
dp0 = 0、dp1 = 0：对应空前缀。两个都取 0 而不是把dp1设成正无穷，是因为「空串以 1 结尾」在这里不是非法状态，而是「1 区域尚未开始」，代价为 0 才能让首字符的min(dp0, dp1)得到正确结果。- 从左到右扫描每个字符：DP 的推进方向必须与「单调递增」的方向一致，从右往左会让转移条件反过来。
- 先算
newDp1 = min(dp0, dp1) + (c == '0' ? 1 : 0)：取min体现了「1 区域可以从任意位置开始」——要么此刻刚从全 0 切换过来（dp0），要么之前已经在 1 区域（dp1）。- 再更新
dp0 = dp0 + (c == '1' ? 1 : 0)：注意右边用的是旧的dp0，且没有min。因为末位为 0 要求前面全是 0，唯一的来源就是上一位也为 0，绝不能从dp1转移。- 最后
dp1 = newDp1：三行的顺序不能打乱。若先写dp0再算dp1，min里用到的就是本轮已改写的dp0，等于允许「同一位既算作 0 结尾又算作 1 的前驱」，结果偏小。- 返回
min(dp0, dp1)：合法串的末位可以是 0（全 0 串）也可以是 1，取较小者。只返回dp1会在"000"这类输入上答错。以
s = "010110"走一遍，正确答案是 2。初始
dp0 = 0、dp1 = 0。第 1 位
'0'：newDp1 = min(0,0) + 1 = 1（要把0翻成1）；dp0 = 0 + 0 = 0（本来就是 0，不用翻）；dp1 = 1。状态：dp0 = 0、dp1 = 1。第 2 位
'1'：newDp1 = min(0,1) + 0 = 0（前缀01保持原样就是合法的）；dp0 = 0 + 1 = 1（要把这个1翻成0）；dp1 = 0。状态：dp0 = 1、dp1 = 0。第 3 位
'0'：newDp1 = min(1,0) + 1 = 1（前缀011，把第 3 位翻成 1）；dp0 = 1 + 0 = 1（前缀000，仍是把第 2 位的 1 翻掉那一次）；dp1 = 1。状态：dp0 = 1、dp1 = 1。第 4 位
'1'：newDp1 = min(1,1) + 0 = 1；dp0 = 1 + 1 = 2（要把第 4 位也翻成 0）；dp1 = 1。状态：dp0 = 2、dp1 = 1。第 5 位
'1'：newDp1 = min(2,1) + 0 = 1；dp0 = 2 + 1 = 3；dp1 = 1。状态：dp0 = 3、dp1 = 1。第 6 位
'0'：newDp1 = min(3,1) + 1 = 2（把末位翻成 1，得到011111，共翻了第 3 位和第 6 位两次）；dp0 = 3 + 0 = 3（全翻成 0 要翻掉三个 1）；dp1 = 2。状态：dp0 = 3、dp1 = 2。返回
min(3, 2) = 2。验证：把下标 2 的0翻成1、下标 5 的0翻成1，得到011111，确实单调递增且只用了 2 次。再看更新顺序为什么要紧：假设在第 2 位先执行
dp0 = 0 + 1 = 1，再算newDp1 = min(1, 1) + 0 = 1，dp1会从正确的 0 变成 1，后续每一步都跟着偏大，最终返回 3 而不是 2。
代码实现
class Solution {
public int minFlipsMonoIncr(String s) {
int dp0 = 0;
int dp1 = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int newDp1 = Math.min(dp0, dp1) + (c == '0' ? 1 : 0);
dp0 = dp0 + (c == '1' ? 1 : 0);
dp1 = newDp1;
}
return Math.min(dp0, dp1);
}
}
func minFlipsMonoIncr(s string) int {
dp0, dp1 := 0, 0
for i := 0; i < len(s); i++ {
c := s[i]
newDp1 := min(dp0, dp1)
if c == '0' {
newDp1++
}
if c == '1' {
dp0++
}
dp1 = newDp1
}
return min(dp0, dp1)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n)$。每个字符只被访问一次，循环体内是常数次比较、加法和取小，没有嵌套。
- 空间复杂度：$O(1)$。只保留
dp0、dp1和一个临时变量，不开前缀和数组，也不复制字符串。
关键点总结
- 把「合法性只依赖末位状态」这一观察找出来，就能把指数级的历史压缩成两个标量——这是所有状态机 DP 的共同起点。
- 两个状态的转移不对称才是本题的考点：末位为 0 只能从 0 来（前面必须全 0），末位为 1 可以从 0 或 1 来。谁能取
min、谁不能，必须能一句话说清理由。- 滚动更新时的赋值顺序承载了「转移用的是上一位的值」这一语义，临时变量不是可有可无的优雅，而是正确性的必需。
- 初值
dp0 = dp1 = 0表达的是「空前缀，1 区域尚未开始」，把dp1设成正无穷会让首个字符无法进入 1 状态。- 答案取 $\min(dp0, dp1)$，因为全 0 串也是合法的单调递增串；只返回
dp1会在"000"、"10"这类输入上答错。- 面试视角：先给出「枚举分界点 + 前缀和」的 $O(n)$ 解证明思路，再升级为状态机 DP 并强调 $O(1)$ 空间与可推广性，是这题最有层次的答法。被追问时能指出「本题等价于把串分成 0 段和 1 段两部分」通常是加分项。
易错点总结
dp0的转移里加了min(dp0, dp1)："10"会算出dp0 = 0，等于允许1后面再接0，返回 0 而正确答案是 1。dp1的转移里只用dp1不取min：1 区域就无法从全 0 前缀开启，"00"的dp1会一路累加成 2，虽然最终min仍取到dp0 = 0侥幸正确，但"0011"之类会算大。- 先更新
dp0再算dp1："010110"会返回 3 而不是 2，因为min里读到的是本轮已改写的dp0，相当于同一位被重复计费。- 返回
dp1而不是min(dp0, dp1)："000"会返回 3（把三位全翻成 1），正确答案是 0。- 返回
dp0而不是min："111"会返回 3，正确答案是 0。dp1初值设成正无穷：首个字符时min(dp0, dp1)仍能取到dp0，看似没事，但若实现中写成dp1 + ...就会溢出；更重要的是它错误暗示「空串不能以 1 结尾」。- 代价判断写反：末位取 0 时对
c == '0'计费、末位取 1 时对c == '1'计费，"01"会返回 2 而正确答案是 0。翻转只在「目标值与当前字符不同」时才发生。- 从右往左扫描但沿用同一套转移：单调方向被反过来，
"10"会返回 0。若要反向 DP，两个状态的转移条件必须同步镜像。- 用
int之外的更窄类型或忘记n的规模：串长 $10^5$，最坏翻转次数也是 $10^5$，int足够；但若误用char或short累加会溢出。- 误以为只能把 0 翻成 1：题目允许双向翻转，
"110"的最优解是把两个1翻成0（代价 2）与把0翻成1（代价 1）中取小，答案是 1；只允许单向会算成 2。- 把「单调递增」理解成严格递增：串里可以有连续多个 0 或连续多个 1，
"0011"合法且答案为 0；按严格递增理解会得出无解或错误代价。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 092. 将字符串翻转到单调递增 | 中等 | 与本题同题，可直接套用 |
| 801. 使序列递增的最小交换次数 | 困难 | 同为「换/不换」两状态 DP，但转移要同时校验两个数组的相邻大小关系 |
| 121. 买卖股票的最佳时机 | 简单 | 「持有/不持有」两状态滚动，与本题的 0/1 状态机结构完全同构 |
| 309. 买卖股票的最佳时机含冷冻期 | 中等 | 状态扩到三个，更新顺序的坑与本题一模一样，是练习临时变量的好题 |
| 53. 最大子数组和 | 中等 | 同样把历史压缩成「以当前位置结尾的最优值」，答案在扫描中取极值 |
| 300. 最长递增子序列 | 中等 | 同为「递增」主题，但状态无法压成常数个，需要 $O(n)$ 的 dp 数组 |