题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解答

如果我们想找到一个数组中的“山顶”，应该怎么做呢，可以考虑从左往右和从右往左两次遍历，取均为上坡结束的位置即可。

这道题有类似的思路。我们只需要找到一个分界点，在分界点左侧所有1变成0，右侧所有0变成1，这样就可以实现字符串的所谓递增了。问题在于如何寻找这个分界点。

为了只有一次项的时间复杂度，我们可以考虑两次遍历的方法，定义两个数组：

left_zero_to_one和right_one_to_zero，维度都是n+1，n是S的长度，+1的原因是考虑下标的余量，以及两个数组的对应。如果以i为分界点，这里i在0和n之间，把S[i-1]及其左侧作为左半部分（需要变成全零的左半段），把S[i]及其右侧作为右边半部分（需要变成全一的右半段），left_zero_to_one[i]表示的是以S[i-1]结尾的连续子串转化为0需要进行的翻转次数，right_one_to_zero[i]表示的是以S[i]开头的连续子子串转化为1需要进行的翻转次数。

这两个数组是很好求的，只需要两次遍历及计数即可。有了这两个数组，每个位置i处对应的总的翻转次数就有了，直接相加就好。从中选择总翻转次数最小的作为结果返回。

class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:

        left_zero_to_one = [0 for _ in range(len(S)+1)]
        for i in range(len(S)):
            left_zero_to_one[i + 1] = left_zero_to_one[i]
            if S[i] == "1":
                left_zero_to_one[i + 1] += 1

        right_one_to_zero = [0 for _ in range(len(S)+1)]
        for i in reversed(range(len(S))):
            right_one_to_zero[i] = right_one_to_zero[i + 1]
            if S[i] == "0":
                right_one_to_zero[i] += 1

        return min(a + b for a, b in zip(right_one_to_zero, left_zero_to_one))

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析