LeetCode LCR 092. 将字符串翻转到单调递增
题目描述
题意分析
每次可以把二进制串的一位在
0和1之间翻转，求变成单调递增串的最少次数。这里允许相等，所以合法形式是若干个0后面跟着若干个1，全0、全1也都合法。每个合法目标都由一个分界决定：分界左侧全部变成
0，右侧全部变成1。因此只需比较所有分界的修改费用，而不用逐个尝试翻转组合。
解法：枚举 0 与 1 的分界
核心思路
[!blue]
设分界为
p，表示前p位要变成0。左侧原有的1要翻转，右侧原有的0要翻转，其他字符已经正确。因此费用是“左侧1的数量 + 右侧0的数量”。用
left0、right0分别维护两侧的0数量。左侧长度为p，其中1的数量就是p - left0，所以当前费用为p - left0 + right0。分界右移一位时，只有刚跨过的字符改变归属。若它是
0，就让right0减一、left0加一；若它是1，两个零计数都不变。代码把字符转换为数值x，再用x ^ 1得到“是否为零”的指示值，完成同样的更新。先统计全串零数，初始分界在最左端：
left0 = 0，right0为全部零数。此时全变成1的费用是right0，全变成0的费用是n - right0，代码先把两个端点纳入答案，再逐位右移分界并取最小值。所有合法目标都被覆盖，每个候选费用又是准确的，最小值就是最少翻转次数。
解题步骤
- 统计全串零数，初始化
left0 = 0、right0和两个端点方案的最小费用。- 每次把一个字符移入左侧，同步调整两侧的零数。
- 用当前前缀长度减去
left0，再加right0，更新最小费用。Java 的循环变量i就是前缀长度；Go 的字符下标从零开始，因此前缀长度是i + 1。- 分界移到末尾后返回答案。单字符、全零或全一的输入都能通过端点分界得到零次翻转。
代码实现
class Solution {
public int minFlipsMonoIncr(String s) {
int n = s.length();
// left0：前缀中 0 的个数；right0：后缀中 0 的个数。
int left0 = 0;
int 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)$，先统计一次，再线性移动分界，每次只更新一个字符的贡献。
- 空间复杂度：$O(1)$，只保存两侧零数和最小费用。
关键点总结
[!green]
- 单调递增的二进制串可由一个分界完整表示，分界两侧允许为空。
- 费用只统计不符合目标的字符：左侧的
1与右侧的0。- 分界移动时只需更新跨过的一个字符，无需重新统计整个前后缀。
- 先更新计数再计算新分界的费用，前缀长度要与当前分界一致。
易错点总结
[!yellow]
- 目标形式允许全 0 或全 1，分界可以在两端，循环或初始化至少覆盖它们。
- 修改代价是左侧 1 的数量加右侧 0 的数量，不能把已符合目标的字符也计费。
- 分界移动时两侧计数同步变化；非严格单调允许重复字符。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1653. 使字符串平衡的最少删除次数 | 中等 | 同样让两类字符按先后顺序排列，原题通过删除修正，本题通过翻转修正。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！