问题描述

​ 如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。

​ 我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

​ 返回使 s 单调递增 的最小翻转次数。

示例1：

1
2
3
输入：s = "00110"
输出：1
解释：我们翻转最后一位得到 00111.

示例2：

1
2
3
输入：s = "010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。

示例3：

1
2
3
输入：s = "00011000"
输出：2
解释：我们翻转得到 00000000。

解题思路

​ 对于一个字符串分析，最终的反转结果必然是：[0,i)--->0 and [i,s.length())---->1的结果，所以我们可以使用一个计数器记录全部的0 ，记录完成后进行遍历：

​ 我们每次遍历一个字符，计算处在此字符下需要反转的次数

  • 下面对于几个遍历量的解释：
    • n0 : 未遍历到的0；n1 :已经遍历到的1 ;n1+n0 :表示遍历到当前字符的时候需要的反转次数
    • min : 记录遍历到当前字符时所需要的最小反转次数

解释为什么n0+n1是当前遍历到字符的反转次数：

就是对于上述最终的情况中的i进行枚举，$i \in [0,s.length()-1]$ ,从这个区间中逐个枚举，n0表示第二部分中0的个数，n1表示第一部分中1的个数，实际要求，第一部分全部为0，第二部分全部为1，所以反转的总次数为n0+n1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int minFlipsMonoIncr(String s) {
    int n0 = 0;
    int n1 = 0;
    // 遍历字符串得到字符串中‘0’的个数
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '0') {
            n0++;
        }
    }
    // 初始化，最小值 ===> ‘0’和‘1’数量的较小的一个
    int min = Math.min(n0, s.length() - n0);
    for (int i = 0; i < s.length(); i++) {
        // n0+n1 表示当前需要的转化的次数
        if (s.charAt(i) == '0') {
            // 遍历到‘0’,标记‘0’的计数器减一
            // n0 表示未遍历到的‘0’的个数，表示需要对于未遍历到的部分0需要转成1
            n0--;
        } else {
            // 遍历到‘1’,标记‘1’的计数器减一
            // n1 表示已经遍历到的‘1’的个数，表示需要对于已经遍历到的部分'1'需要转成'0'
            n1++;
        }
        // 更新最小值
        min = Math.min(n0 + n1, min);
    }
    return min;
}