难度: Medium
原题连接
内容描述
A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly 0.)
We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.
Return the minimum number of flips to make S monotone increasing.
Example 1:
Input: "00110"
Output: 1
Explanation: We flip the last digit to get 00111.
Example 2:
Input: "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.
Example 3:
Input: "00011000"
Output: 2
Explanation: We flip to get 00000000.
Note:
1 <= S.length <= 20000
S only consists of '0' and '1' characters.
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******
我们就这样想吧，要想最后满足要求，我们的字符串S肯定是'000000001111111'的形式，可以全为0还可以全为1
因此我们每种情况都考虑一下，取其中改变次数最小的那个次数，
即让前i个字符都变成0，后面len(S)-i个字符都变成1所需要的次数
class Solution(object):
def minFlipsMonoIncr(self, S):
"""
:type S: str
:rtype: int
"""
if not S or len(S) <= 1:
return 0
count_0, count_1 = [0] * (len(S)+1), [0] * (len(S)+1)
for i, v in enumerate(S):
if v == '0':
count_0[i+1] = count_0[i] + 1
count_1[i+1] = count_1[i]
else:
count_0[i+1] = count_0[i]
count_1[i+1] = count_1[i] + 1
res = sys.maxsize
for i in range(len(S)+1): # 代表S前面i个字符全都是'0'
res = min(res, count_1[i] + count_0[-1] - count_0[i])
return res思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******
跟刚才的思想一样，我们只要把左边的1全部变成0， 右边的0全部变成1，然后取最小的那次就行了
class Solution(object):
def minFlipsMonoIncr(self, S):
"""
:type S: str
:rtype: int
"""
r0, r1, l0, l1 = 0, 0, 0, 0
for i, c in enumerate(S):
if c == '0':
r0 += 1 # 从idx为0开始，右边有多少个0
else:
r1 += 1 # 从idx为0开始，右边有多少个1
res = r0
for i, c in enumerate(S):
if c == '0':
r0 -= 1
l0 += 1
else:
r1 -= 1
l1 += 1
res = min(l1 + r0, res) # 此时我们要将左边的1全部变成0，右边的0全部变成1
return res