LeetCode LCR 092. 将字符串翻转到单调递增
目录
题目描述
题意分析
给一个只含
'0'和'1'的字符串s，每次操作可以把某一位翻转（0 变 1 或 1 变 0），求把s变成单调递增所需的最少翻转次数。
先把「单调递增」翻译成可操作的形式。对二进制串而言，单调递增等价于不存在某个 1 排在某个 0 前面，也就是整串形如「若干个 0 后面跟着若干个 1」。注意两端是允许为空的：全 0 合法（零个 1），全 1 合法（零个 0），空的分界也合法。
这个刻画立刻给出问题的结构：任何一个合法的目标串都由一个「分界位置」唯一确定——分界左边全填 0，右边全填 1。长度为
n的串有n + 1个可能的分界（从「全是 1」到「全是 0」）。于是原问题变成：在这n + 1个候选目标里，找一个与s差异最小的。
差异数也很好算：把某个分界记作
i，表示前i位要变成 0、后n - i位要变成 1，那么代价 = 前i位中 1 的个数（这些要翻成 0）+ 后n - i位中 0 的个数（这些要翻成 1）。至此题目已经完全数值化，不再有任何隐含条件。
约束
1 ≤ s.length ≤ 10^5，这个规模明确排除了对每个分界都重新扫一遍的 $O(n^2)$ 做法，必须让代价随分界移动而增量更新。字符只有 0 和 1 两种，答案上界是n（最多每位都翻一次），int完全够用。
边界：
n = 1时无论"0"还是"1"都已单调，答案 0；全 0 或全 1 的串答案也是 0，这要求分界能取到最两端；答案可能为 0，初始值不能设成 1 或负数。
解法：动态规划递推
核心思路
朴素做法是枚举全部
n + 1个分界，对每个分界扫一遍字符串数出两侧的错位字符，总量 $O(n^2)$，n = 10^5时上百亿次操作，必然超时。瓶颈在于相邻两个分界的代价其实只差一个字符，却每次都从头重算。
关键观察是：分界从
i右移到i + 1时，只有第i个字符从「属于右半段」变成了「属于左半段」，其余字符的归属完全不变。所以只要维护两个计数器就够了：
left0表示左半段（前缀）里 0 的个数，right0表示右半段（后缀）里 0 的个数。有了它们，分界i的代价可以写成i - left0 + right0——前缀长度i减去前缀里 0 的个数就是前缀里 1 的个数（要翻成 0 的），加上后缀里 0 的个数（要翻成 1 的）。
要维持的不变量是：处理到分界
i时，left0恰是s[0..i-1]中 0 的个数，right0恰是s[i..n-1]中 0 的个数，两者之和恒等于全串 0 的总数。每右移一格，若移过去的字符是 0，则right0减一、left0加一；若是 1，两者都不变。代码里用x ^ 1把字符值转成「是否为 0」的 0/1 量，一行完成这个条件更新，避免写分支。
初始化对应分界
i = 0：前缀为空，left0 = 0，right0等于全串 0 的总数，代价就是right0（把所有 0 翻成 1，即目标为全 1 串）。另一个端点i = n的代价是n - right0（把所有 1 翻成 0，即目标为全 0 串）。答案初值取这两者的较小值，随后循环再逐个比较中间的分界。
解题步骤
- 先统计全串 0 的总数：一趟循环把
right0累加出来。这一步既是i = 0时的代价，也是后续增量更新的起点。
- 用两个端点初始化答案：
answer = min(right0, n - right0)，分别对应「目标全 1」和「目标全 0」。先把两端放进候选，可以让主循环专心处理中间分界，也保证了全 0 / 全 1 输入能得到 0。
- 主循环让分界从 1 扫到 n：第
i轮处理的是「刚刚被划入前缀的那个字符」s[i-1]。循环变量取分界而不是字符下标，是为了让代价公式i - left0 + right0里的i直接就是前缀长度。
- 无分支地更新两个计数器：把字符转成
x（'0'为 0，'1'为 1），则x ^ 1就是「该字符是不是 0」。执行right0 -= x ^ 1与left0 += x ^ 1，字符是 1 时两句都加减 0，等于什么也没做。用异或代替if只是写法上的简洁，语义与分支判断完全一致。
- 更新答案：
answer = min(answer, i - left0 + right0)。i - left0是前缀中 1 的个数，right0是后缀中 0 的个数，两者之和就是把串改造成「前i位全 0、其余全 1」的代价。
以
s = "00110"走一遍，n = 5。
预处理：全串有 3 个 0（下标 0、1、4），所以
right0 = 3，left0 = 0。答案初值min(3, 5 - 3) = 2，对应「全变成 0 要翻两个 1」这个方案。
i = 1，划入的字符是s[0] = '0'：right0变 2，left0变 1。代价1 - 1 + 2 = 2（前缀"0"里没有 1，后缀"0110"里有两个 0）。答案仍为 2。
i = 2，划入s[1] = '0'：right0变 1，left0变 2。代价2 - 2 + 1 = 1（前缀"00"无需改动，后缀"110"只有末尾一个 0 要翻成 1）。答案更新为 1。
i = 3，划入s[2] = '1'：两个计数器都不变，仍是right0 = 1、left0 = 2。代价3 - 2 + 1 = 2（前缀"001"里的那个 1 要翻成 0，后缀"10"里的 0 要翻成 1）。答案保持 1。
i = 4，划入s[3] = '1'：计数器不变。代价4 - 2 + 1 = 3。答案保持 1。
i = 5，划入s[4] = '0'：right0变 0，left0变 3。代价5 - 3 + 0 = 2（全变成 0，要翻掉两个 1）。答案保持 1。
返回 1，对应把末尾的 0 翻成 1 得到
"00111"，确实单调递增且只改了一位。若忘记初始化时考虑i = 0这个端点，输入"111"会得到min从主循环第一轮开始比较，虽然本例仍能得到 0，但输入"11"时若把答案初值写成n之外的错误值就会偏大。
代码实现
class Solution {
public int minFlipsMonoIncr(String s) {
int n = s.length();
// left0：前缀中 0 的个数；right0：后缀中 0 的个数。
int left0 = 0, right0 = 0;
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == '0') {
++right0;
}
}
// 两个端点：目标全 1 的代价是 right0，目标全 0 的代价是 n - right0。
int answer = Math.min(right0, n - right0);
// i 是分界：前 i 位变 0，其余变 1。
for (int i = 1; i <= n; ++i) {
int x = s.charAt(i - 1) == '0' ? 0 : 1;
// x ^ 1 即「该字符是不是 0」，字符为 1 时两句都不产生变化。
right0 -= x ^ 1;
left0 += x ^ 1;
// i - left0 是前缀中 1 的个数，right0 是后缀中 0 的个数。
answer = Math.min(answer, i - left0 + right0);
}
return answer;
}
}
func minFlipsMonoIncr(s string) int {
n := len(s)
// left0：前缀中 0 的个数；right0：后缀中 0 的个数。
left0, right0 := 0, 0
for _, c := range s {
if c == '0' {
right0++
}
}
// 两个端点：目标全 1 的代价是 right0，目标全 0 的代价是 n - right0。
answer := min(right0, n-right0)
for i, c := range s {
x := 0
if c == '1' {
x = 1
}
// x ^ 1 即「该字符是不是 0」，字符为 1 时两句都不产生变化。
right0 -= x ^ 1
left0 += x ^ 1
// 分界为 i+1：前 i+1 位变 0，其余变 1。
answer = min(answer, i+1-left0+right0)
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，一趟统计全串 0 的个数，再一趟枚举分界并增量更新，共两次线性扫描，每格只做常数次加减与比较。
- 空间复杂度：$O(1)$，只用了
left0、right0、answer等几个整数计数器，不随字符串长度增长。原串只读不改，无需额外副本。
关键点总结
- 把「求最少修改次数」转化成「枚举所有合法目标，取差异最小」是这类题的通用起手式。前提是合法目标能被一个简单参数完整刻画——本题是分界位置，参数只有一维，于是问题立刻变成一维枚举。
- 相邻候选之间只差一个元素时，用增量维护把 $O(n^2)$ 降到 $O(n)$。这就是前缀和 / 滑动统计的本质，凡是「枚举分割点并计算两侧统计量」的题都该条件反射地想到它。
- 两个端点分界必须被纳入候选，它们对应「全 1」和「全 0」两个目标。忘记它们会在全 0 或全 1 的输入上给出非零答案。
i - left0就是前缀中 1 的个数，这类「用长度减去某类计数得到另一类计数」的技巧，可以省掉一半的计数器，值得记住。- 面试视角：这道题也可以写成两个状态的线性 DP（当前位最终是 0 或 1 分别的最小代价），两种写法都是标准答案。被问到时能同时说出「分界枚举 + 前缀统计」和「二状态 DP」，并指出两者复杂度相同、前者更容易解释，是很好的加分点。
易错点总结
- 只枚举
1..n-1的中间分界：s = "111"会漏掉「保持全 1」这个零代价方案，输出 1 而不是 0。- 答案初值设成 0：
s = "10"会直接返回 0，而正确答案是 1，因为最小值永远不会被更新上去。- 代价写成
left0 + right0：s = "00110"在i = 2处会算出2 + 1 = 3，把前缀里的 0（本来就不用改）也算进了代价。- 代价写成
i - left0 + (n - i - right0)：这算的是后缀中 1 的个数，s = "00110"会在全 0 目标处得到 0，等于把「后缀要变成 1」写反成了「后缀要变成 0」。- 对每个分界重新扫一遍统计两侧计数：
s为 10 万个字符时是 $10^{10}$ 量级操作，直接超时。- 忘记先统计全串 0 的总数就进入主循环：
right0从 0 开始递减会变成负数，s = "00110"输出负值。- 更新顺序写成先
left0 += x ^ 1再用i - left0，却把right0的减法放到取答案之后：s = "010"时两个计数器不同步，代价算出的是不存在的中间态。- 用
s.charAt(i)而不是s.charAt(i - 1)：i = n时越界抛异常；即使不越界，整个统计也会错位一位。- 把单调递增误读成严格递增：
s = "00"会被认为需要修改，而全 0 本就合法，答案应为 0。- 误以为必须让 0 和 1 各占一半或至少各有一个：
s = "1"的正确答案是 0（视作零个 0 加一个 1），强行要求两端非空会输出 1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 926. 将字符串翻转到单调递增 | 中等 | 与本题完全同题，代码可原样提交 |
| 738. 单调递增的数字 | 中等 | 同样以单调性为目标，但字符集是 0~9 且只能减小，改用贪心从高位借位 |
| 801. 使序列递增的最小交换次数 | 困难 | 同为「最少修改使序列有序」，但每位的选择是换或不换的二状态 DP |
| 995. K 连续位的最小翻转次数 | 困难 | 也是 0/1 串的最少翻转，但每次必须翻固定长度的一段，需差分记录影响 |
| 845. 数组中的最长山脉 | 中等 | 同样枚举分界点并结合两侧预处理，只是两侧要求的是递增与递减长度 |
| 42. 接雨水 | 困难 | 前后缀统计的经典题，可对照体会「左右两侧信息同时维护」的通用手法 |
| 1109. 航班预订统计 | 中等 | 差分数组的入门题，是「增量更新代替重复求和」这一思想的另一种形态 |
| 198. 打家劫舍 | 中等 | 若改写成二状态线性 DP，本题的转移结构与它高度相似，可对照理解 |