926. Flip String to Monotone Increasing
给你一个只有 0 和 1 的 string s，问你最少要翻转几次才能把它变为递增
翻转:把某个 0 变成 1 或者是把某个 1 变成 0
Example 1:
Input: s = "00110"
Output: 1
翻转成 00111
Example 2:
Input: s = "010110"
Output: 2
翻转成 000111/011111
Example 3:
Input: s = "00011000"
Output: 2
翻转成 00000000
思路:
1.要让 string 是递增就必须是一串 0 接着一串 1
也就是说对于某个 index = i, s[:i] 全部都是 0, s[i:] 全部都是 1
我们就去遍历所有 i, 看看要让 s[:i] 翻转成 0 的次数加上 s[i:] 翻转成 1 的次数
在哪个 i 时会是最小
2.要把 s[:i] 翻转成 0 的次数其实就是算 s 的 prefix sum, O(n)解决
算完全部后再反著做 s[i:], iterate i = len(s)-1 ~ 0 然后一边检查最小值就好
时间 O(n) 空间 O(n)
3.看了讨论区有种更好的做法是用类似 dp 的概念
假设已经知道要把 s[:i] 翻转成递增的最小次数 n 了
那 s[:i+1] 就有两种可能
一种是 s[i] 变成/保持 1, 这种状况下可以直接拿 n 来用
因为 s[:i] 翻转 n 次已经变成递增了, s[i] 的 1 可以直接接在后面
这种情况下最佳解就会是 n + (s[i] == 0), 也就是如果 s[i] == 0 要把他转成 1
另一种是 s[i] 变成/保持 0, 这种状况下 n 就没用了
因为 s[:i] 转完后有可能是 1 结尾, s[i] 的 0 不能接
所以这里最佳解就只能是把 s[:i] 和 s[i] 全部都变成 0, 也就是 prefix sum
最后再比两种状况哪种比较小就好
这种做法比刚刚那种好的原因是可以只 iterate i 一次, 也不用记整个 prefix sum
时间一样是 O(n) 空间变成 O(1)
Python code:
class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
one = opt = 0
for c in s:
one += (c == '1')
opt = min(one, opt + (c == '0'))
return opt