题目描述

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

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

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

样例

输入："00110"
输出：1
解释：我们翻转最后一位得到 00111。

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

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

限制

• 1 <= S.length <= 20000
• S 中只包含字符 '0' 和 '1'。

算法

(动态规划) $O(n)$

1. 设 $f(i)$ 表示以位置 $i$ 结尾时，还没有跨越 01 分界时的最少翻转次数；$g(i)$ 表示以位置 $i$ 结尾时，已经跨越了 01 分界时的最少翻转次数。
2. 初始时，如果 $S(0)$ 为 0，则 $f(0) = 0, g(0) = 1$；否则，$f(0) = 1, g(0) = 0$。其余待定。
3. 转移时
   • 如果当前位置为 0，$f(i) = f(i - 1)$，因为没有跨越分界时，只能从上一次没有跨越来转移，但无需翻转。$g(i) = \min(f(i - 1), g(i - 1)) + 1$，因为此时已经跨越了分界，可以从上一次已跨越或未跨越转移，但需要将 0 翻转为 1。
   • 如果当前位置为 1，$f(i) = f(i - 1) + 1$，因为没有跨越分界时，只能从上一次没有跨越来转移，也需要将 1 翻转为 0。$g(i) = \min(f(i - 1), g(i - 1))$因为此时已经跨越了分界，可以从上一次已跨越或未跨越转移，但无需翻转。
4. 最终答案为 $\min(f(n - 1), g(n - 1))$。
5. 可以仅使用两个变量来进行常数优化。

时间复杂度

• 状态数为 $O(n)$，转移时间为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 优化后，仅需要常数的额外空间。

Go 代码

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

func minFlipsMonoIncr(S string) int {
    n := len(S)
    var f, g int

    if S[0] == '0' {
        f = 0
        g = 1
    } else {
        f = 1
        g = 0
    }

    for i := 1; i < n; i++ {
        if S[i] == '0' {
            g = min(f, g) + 1
        } else {
            g = min(f, g)
            f++
        }
    }

    return min(f, g)
}