将字符串翻转到单调递增 图解题解

单调递增到底长什么样，这题要最少翻几次

给一个只由 0 和 1 组成的字符串 s，每次能把某位翻转（0 改成 1 或 1 改成 0）。目标是让整串单调递增：出现 1 后右边不准再有 0，即形如 0…01…1（前段全 0、后段全 1，两段可空）。求最少翻几位。比如 s="00110"，最少 1 次就变单调，答案是 1，翻哪一位后面逐位算。

把每个切点都试一遍，为什么会慢下来

长 n 的 s，单调结果无非在某处切一刀：左边全是 0、右边全是 1，切点有 n+1 个候选（含全 0、全 1 两个极端）。n 个切点逐个试就是 O(n²)（大 O 记号，描述规模变大时操作数怎么涨）：每个切点把左边每个 1 翻成 0、右边每个 0 翻成 1，扫左右两侧数出翻转数取小，串一长就拖不动。

一趟扫描要盯住哪两笔账

其实不必为每个切点重新数。从左往右扫一遍、维护两笔账就够——这就是动态规划（把大问题拆成一串能顺推的小问题，前面算好的直接喂给后面、不重算）的思路。第一笔账 ones：前缀（前缀 = 从头到当前这一段）里到眼下有几个 1；把这段前缀压成全 0，就得翻掉这些 1，代价正好是 ones。第二笔账 flips：把眼下前缀改成单调最少翻几次。扫完整串的 flips 就是答案。

见 0 时的那行取小，到底在挑什么

每读一位，两笔账各自更新。读到 1：它接在已有的 1 后面不破坏『0 在前、1 在后』，不用翻，flips 不变，只 ones 加一。读到 0 才是关键：它破坏了单调，补救对应两种切法。一是把它划进后段、翻成 1，代价是原 flips 加一，即 flips+1；二是让切点落在它之前，前缀作全 0 段收尾，把前面所有 1 翻成 0，代价正好是 ones。取便宜的，于是 flips = min(flips+1, ones)——这行 min 就是在『顶当前 0』和『压光前面的 1』里挑省的，枚举切点被压进这一步。

拿 s=00110 逐位把两笔账走一遍

开局 ones=0、flips=0。第 0 位是 0，前面没有 1，flips=min(0+1, 0)=0。第 1 位也是 0，flips 仍 0。第 2、3 位都是 1，不用翻，ones 加到 2，flips 仍 0。第 4 位是 0，前面攒了 2 个 1：翻它自己要 flips+1=1 次，翻光前面 2 个 1 要 ones=2 次，取小 flips=min(1, 2)=1。扫完返回 flips=1，即把最后这个 0 翻成 1、得 00111，正对上题面答案 1。

见 0 只顾着翻它自己，长串上为什么会平白多翻

复杂度：只扫一遍，每位一次加法或取小，时间 O(n)；只留 ones、flips 两个数（只留最近几笔账、循环覆盖旧值，叫滚动变量），空间 O(1)。真正易错的是那行取小：见 0 只记得 flips+1 把它顶成 1，漏了『翻光前面的 1』这条路。碰上前面 1 多、后面又连来一串 0 的串就吃亏：一味翻 0 越翻越多，其实把那几个 1 压成全 0 更省，漏掉 ones 答案会偏大。边界顺带想清：空串、全 0、全 1 本就单调，一次都不用翻。

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 flips

C++

#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;
    }
}