LeetCode 926中等DP/贪心
将字符串翻转到单调递增 图解题解
这道题到底在问什么
给定二进制字符串 s。可把任意位 0 改 1 或 1 改 0。求使 s 单调递增（形如 0…01…1）所需的最少翻转次数。
- 输入
- s="00110"
- 输出
- 1 （把第 3 位的 1 翻成 0 → 00010？不，翻末位前的 1，得 00011）
最优解：一步一步想明白
- 3记住「见 1 则 ones+1；见 0 则 flips = min(flips+1, ones)」，下面每帧都在套它。
- 4开局两个计数都为 0。我们从左往右逐位读：见 1 累加 ones，见 0 在「翻自己」与「翻光前面的 1」之间取小。
- 5读到第 0 位是 0，但前面一个 1 都还没有，它天然就在合法位置，不构成任何冲突。
- 6结算：前面无 1，这个 0 不用动，flips 维持 0。
- 7读到第 1 位是 1（紫色）。1 能不能直接留下？能——1 接在已有的 1 后面不破坏「0 在前 1 在后」的单调。
- 8结算：这个 1 不用翻，ones 累加到 1。flips 保持 0。继续下一位。
- 9读到第 2 位是 0（红色）。可前面已经有 1 个 1 了，0 出现在 1 后面破坏了单调，必须想办法补救。
- 10结算：两条补救路取小——翻它自己要 1 次，翻光前面 1 个 1 要 1 次，于是 flips = 1（两者代价一样，任选其一，这里按翻当前 0 来讲）。
- 11读到第 3 位是 1（紫色）。1 能不能直接留下？能——1 接在已有的 1 后面不破坏「0 在前 1 在后」的单调。
- 12结算：这个 1 不用翻，ones 累加到 2。flips 保持 1。继续下一位。
- 13读到第 4 位是 1（紫色）。1 能不能直接留下？能——1 接在已有的 1 后面不破坏「0 在前 1 在后」的单调。
- 14结算：这个 1 不用翻，ones 累加到 3。flips 保持 1。继续下一位。
- 15读到第 5 位是 0（红色）。可前面已经有 3 个 1 了，0 出现在 1 后面破坏了单调，必须想办法补救。
- 16结算：两条补救路取小——翻它自己要 2 次，翻光前面 3 个 1 要 3 次，于是 flips = 2（翻当前 0 更省）。
- 17读到第 6 位是 0（红色）。可前面已经有 3 个 1 了，0 出现在 1 后面破坏了单调，必须想办法补救。
- 18结算：两条补救路取小——翻它自己要 3 次，翻光前面 3 个 1 要 3 次，于是 flips = 3（两者代价一样，任选其一，这里按翻当前 0 来讲）。
- 19读到第 7 位是 0（红色）。可前面已经有 3 个 1 了，0 出现在 1 后面破坏了单调，必须想办法补救。
- 20结算：两条补救路取小——翻它自己要 4 次，翻光前面 3 个 1 要 3 次，于是 flips = 3（翻光前面的 1 更省）。
- 21读到第 8 位是 1（紫色）。1 能不能直接留下？能——1 接在已有的 1 后面不破坏「0 在前 1 在后」的单调。
- 22结算：这个 1 不用翻，ones 累加到 4。flips 保持 3。继续下一位。
- 23读到第 9 位是 1（紫色）。1 能不能直接留下？能——1 接在已有的 1 后面不破坏「0 在前 1 在后」的单调。
- 24结算：这个 1 不用翻，ones 累加到 5。flips 保持 3。继续下一位。
- 25读到第 10 位是 0（红色）。可前面已经有 5 个 1 了，0 出现在 1 后面破坏了单调，必须想办法补救。
- 26结算：两条补救路取小——翻它自己要 4 次，翻光前面 5 个 1 要 5 次，于是 flips = 4（翻当前 0 更省）。
- 27全串扫完，flips = 4 就是把 01011000110 变成单调递增所需的最少翻转次数。整个过程一遍扫描、只维护 ones 和 flips 两个数。
⚠️ 容易写错的地方
✗ 错：见 0 只想到「翻自己」
✓ 对：还要和「翻光前面所有 1」比较取小
当前面 1 很少时，把它们全翻成 0 反而更省
✗ 错：见 1 时去动 flips
✓ 对：见 1 只累加 ones，flips 不变
1 接在 1 后面天然合法，无需任何翻转
✗ 错：用二维 DP 开数组
✓ 对：两个滚动变量即可
flips 只依赖前一状态，无需保存整张表
完整代码（Python / C++ / Java）
Python
class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
ones = 0
flips = 0
for ch in s:
if ch == '1':
ones += 1
else:
flips = min(flips + 1, ones)
return flipsC++
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
int minFlipsMonoIncr(string s) {
int ones = 0, flips = 0;
for (char ch : s) {
if (ch == '1') ++ones;
else flips = min(flips + 1, ones);
}
return flips;
}
};Java
import java.util.*;
class Solution {
public int minFlipsMonoIncr(String s) {
int ones = 0, flips = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '1') ones++;
else flips = Math.min(flips + 1, ones);
}
return flips;
}
}复杂度
时间
O(n)
扫一遍字符串
空间
O(1)
只用 ones、flips 两个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 将字符串翻转到单调递增 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这两个变量背后其实是什么 DP？+
设 dp 为「使前缀单调递增的最少翻转」。转移时遇 1 可不翻（dp 不变）也可翻成 0；遇 0 可不翻（要求前面无 1）也可翻成 1。化简后只剩 ones 和 flips 两个滚动量，这就是「DP 降维成常数空间」的典型。
如果允许结果是「若干 1 后接若干 0」呢？+
那是镜像问题，再从右往左跑一遍同样逻辑，或对称地维护 zeros 即可，思路完全一致。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 将字符串翻转到单调递增 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。