中等

问题描述

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

给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = "00011000"
输出：2
解释：翻转得到 00000000

提示：

• 1 <= s.length <= 105
• s[i] 为 '0' 或 '1'

动态规划

比较容易想到动态规划的解法，假设

• $f(i)$ 为字符串 $s_0 \dots s_i$ 翻转为以 $0$ 结尾的 单调递增 字符串所需的最小翻转次数
• $g(i)$ 为字符串 $s_0 \dots s_i$ 翻转为以 $1$ 结尾的 单调递增 字符串所需的最小翻转次数

如果是以 $0$ 结尾，由于字符串需要递增，当 $s_i$ 为 $0$ 时，无需操作 $f(i) = f(i-1)$；当 $s_i$ 为 $1$ 时，需要将 $1$ 翻转为 $0$，操作步数为 $f(i) = f(i-1) + 1$，递推公式如下：

$$f(i) = \begin{cases} 0 & i = 0 \wedge s_i = '0'\\ f(i - 1) & i > 0 \wedge s_i = '0'\\ 1 & i = 0 \wedge s_i = '1'\\ f(i - 1) + 1 & i > 0 \wedge s_i = '1'\\ \end{cases}$$

如果是以 $1$ 结尾，由于字符串需要递增，当 $s_i$ 为 $0$ 时，需要执行一次翻转，因为翻转后 $s_i$ 为 $1$，$s_{i-1}$ 是 $0$ 或 $1$ 都满足递增条件，那么最小操作次数为 $g(i) = min(f(i - 1),g(i - 1)) + 1$；当 $s_i$ 为 $1$ 时，无需操作，那么最小操作次数为 $g(i) = min(f(i - 1),g(i - 1))$，递推公式如下：：

$$g(i) = \begin{cases} 1 & i = 0 \wedge s_i = '0'\\ g(i) = min(f(i - 1),g(i - 1)) + 1 & i > 0 \wedge s_i = '0'\\ 0 & i = 0 \wedge s_i = '1'\\ g(i) = min(f(i - 1),g(i - 1)) & i > 0 \wedge s_i = '1'\\ \end{cases}$$

最终答案为 $min(f(n-1),g(n-1))$，由于 $i$ 只与 $i - 1$ 相关，可以使用滚动数组优化

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$，未进行空间优化复杂度为$O(n)$