leetcode：926. Flip the string to monotonically increasing [prefix and + analog analysis]

analysis

If all 0 Or all 1 No need to analyze
The initial value is set to all 1 The number of
Then we consider a certain 1 Front set to 0, This 1 All the following settings are 1
This requires flipping s[:i] in 1 The number of and s[i + 1:] in 0 The number of
Use prefix and to solve

ac code

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        if s.count('0') * s.count('1') == 0:
            return 0
        minn = s.count('1')
        n = len(s)

        lst1 = list(map(int, s))
        preSum1 = list(accumulate(lst1, initial = 0))
        lst0 = [1 if c == '0' else 0 for c in s]
        preSum0 = list(accumulate(lst0, initial = 0))
        #print(preSum0)
        #print(preSum1)
        for i in range(n):
            if s[i] == '1':
                #now = s[:i].count('1') + s[i + 1:].count('0')
                now = (preSum1[i] - preSum1[0]) + (preSum0[-1] - preSum0[i + 1])
                minn = min(minn, now)
        
        return minn

summary

Simulate and apply prefixes and optimizations
Then note that the initial value is all 1 Reverse into 0 The number of times