---

0926. 将字符串翻转到单调递增

• 标签：字符串、动态规划
• 难度：中等

题目链接

• 0926. 将字符串翻转到单调递增 - 力扣

题目大意

描述：

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

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

要求：

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

说明：

• $1 \le s.length \le 10^{5}$。
• $s[i]$ 为 '0' 或 '1'。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：动态规划

思路

这道题要求将二进制字符串翻转为单调递增（先 $0$ 后 $1$）的最小翻转次数。

我们可以使用动态规划：

• 定义 $dp0$ 表示当前位置结尾为 $0$ 的最小翻转次数。
• 定义 $dp1$ 表示当前位置结尾为 $1$ 的最小翻转次数。

状态转移：

• 如果当前字符是 '0'：
  • $dp0$ 不变（不需要翻转）。
  • $dp1 = dp1 + 1$（需要将 '0' 翻转为 '1'）。
• 如果当前字符是 '1'：
  • $dp0 = dp0 + 1$（需要将 '1' 翻转为 '0'，但这会破坏单调性，所以实际上不能再添加 $0$）。
  • $dp1 = \min(dp0, dp1)$（可以保持 '1' 不变，或者从前面的 $0$ 序列转换过来）。

最终答案是 $\min(dp0, dp1)$，但由于单调递增的字符串可以全是 $0$ 或全是 $1$，所以答案是 $dp1$。

代码

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        dp0 = 0  # 以 0 结尾的最小翻转次数
        dp1 = 0  # 以 1 结尾的最小翻转次数
        
        for ch in s:
            if ch == '0':
                # 当前是 0，保持 0 不需要翻转，变成 1 需要翻转
                dp1 = min(dp0, dp1) + 1
                # dp0 不变
            else:
                # 当前是 1，变成 0 需要翻转（但会破坏单调性），保持 1 不需要翻转
                dp1 = min(dp0, dp1)
                dp0 = dp0 + 1
        
        return min(dp0, dp1)

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串长度。只需要遍历一次字符串。
• 空间复杂度：$O(1)$，只使用了常数个额外变量。