[数据结构与算法]LeetCode 926. Flip String to Monotone Increasing - 亚马逊高频题

A binary string is monotone increasing if it consists of some number of?0's (possibly none), followed by some number of?1's (also possibly none).

You are given a binary string?s. You can flip?s[i]?changing it from?0?to?1?or from?1?to?0.

Return?the minimum number of flips to make?s?monotone increasing.

Example 1:

Input: s = "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:

Input: s = "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: s = "00011000"
Output: 2
Explanation: We flip to get 00000000.

Constraints:

• 1 <= s.length <= 105
• s[i]?is either?'0'?or?'1'.

题目给一个二进制字符串的单调递增性做了定义，如果字符串里所有‘0’（也可能不含‘0’）都在所有的‘1’前面（也可能不含‘1’），那么该二进制字符串就是单调递增的。

给定一个二进制字符串，你可以将字符串里的‘0’翻转成‘1’，或把‘1’翻转成‘0’。问最少要翻转多少次就可以使其变成单调递增的？

根据题目对单调性的定义，把一个二进制字符串变成单调递增的，最终所有‘0’都应该集中在字符串前面，所有‘1’都集中在字符串后面。也就是说我们可以在字符串的任意一个位置把字符串分成前后两部分，把前面部分的‘1’都翻转成‘0’，把后面部分的‘0’都翻转成‘1’，这样就可以把字符串变成单调递增的，因此本题就变成了算出每一个位置把字符串变成递增要翻转的次数，找出翻转次数最少的那个就是答案。对于一个位置，只要知道它前面部分‘1’的个数和后面部分‘0’的个数，两个和就是翻转次数，为了快速算出前后‘1’和‘0’的个数，可以像算数组前缀和一样，先遍历一遍字符串，统计出每个位置到头部‘1’的个数，遍历完之后就可以快速算出任意两个位置之间的‘0’或‘1’的个数。这样再遍历一次字符串，就可以直接算出每个位置前面部分‘1’的个数和后面部分‘0’的个数，由此知道翻转次数，在遍历过程中不断更新翻转次数最小值，遍历完得到的最小值就是把字符串变成单调递增的最少翻转次数。

class Solution:
    def minFlipsMonoIncr(self, s):
        n = len(s)
        res = n

        pre1 = [0] * (n + 1)
        for i in range(n):
            pre1[i + 1] = pre1[i] + int(s[i])

        for i in range(n + 1):
            res = min(res, pre1[i] + (n - i - (pre1[-1] - pre1[i])))

        return res