难度: Medium
如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。
我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。
返回使 s 单调递增 的最小翻转次数。
示例 1：
输入：s = "00110" 输出：1 解释：我们翻转最后一位得到 00111.
示例 2：
输入：s = "010110" 输出：2 解释：我们翻转得到 011111，或者是 000111。
示例 3：
输入：s = "00011000" 输出：2 解释：我们翻转得到 00000000。
提示：
1 <= s.length <= 20000'0' 和 '1'注意：本题与主站 926 题相同： https://leetcode-cn.com/problems/flip-string-to-monotone-increasing/
运行时间: 35 ms
内存: 16.9 MB
class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
counter = 0
for c in s:
if c == '0': counter += 1
res = [counter]
for c in s:
counter = res[-1]
if c == '0': counter -= 1
else: counter += 1
res.append(counter)
return min(res)
首先计算字符串中'0'的数量作为初始的翻转次数，这是因为如果我们把所有的'1'都翻转成'0'，这就是最开始考虑的情况。随后，我们遍历字符串，维护一个动态的翻转次数。对于每个字符，如果它是'0'，则我们之前的计算中已经考虑过将它翻转为'1'的情况，所以现在应当将计数减少1，表示我们保留这个'0'而不是翻转。如果字符是'1'，则我们需要增加翻转次数，因为我们之前的计数是基于将所有'1'翻转为'0'的假设。我们继续更新这个翻转次数直到字符串结尾，每一步都记录当前的翻转次数。最后，返回这些翻转次数中的最小值。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
# 初始时，统计字符串中'0'的数量
counter = 0
for c in s:
if c == '0':
counter += 1
# 使用列表记录每个位置可能的最小翻转次数
res = [counter]
for c in s:
# 更新当前的计数器
counter = res[-1]
if c == '0':
counter -= 1 # 保留'0', 减少翻转计数
else:
counter += 1 # 翻转'1'为'0', 增加翻转计数
res.append(counter)
# 返回所有可能的最小翻转次数
return min(res)
是的，算法一开始将所有的'0'的数量视为初始翻转次数，确实是基于一个假设：如果我们将所有的'1'翻转成'0'，我们将得到一个全'0'的字符串，这是单调递增的。这个计数提供了一个基线，即在最极端的情况下（全翻转为'0'），所需的翻转次数。这个初始计数是为了与后续比较，找到在保持字符串单调递增的前提下，实际所需的最小翻转次数。
在遍历字符串时，增加或减少翻转次数的决策基于当前字符是'0'还是'1'。如果当前字符是'0'，则之前考虑过的将'0'翻转为'1'的操作实际上是不必要的，因为保持'0'有助于保持字符串的单调递增，所以我们将翻转次数减少1。相反，如果当前字符是'1'，为了保持字符串的单调递增，我们需要考虑将这个'1'翻转成'0'，因此翻转次数需要增加1。每次更新都是为了维持或达到单调递增的状态。
是的，列表'res'记录的确是每个位置可能的最小翻转次数，这意味着对于每个字符，算法都是在考虑之前所有字符的情况后，更新当前字符位置的最小翻转次数。这个过程是动态的，每读取一个新字符，就基于之前的结果重新计算一次，确保每一步都是基于最新信息的最优决策。这样，当字符串遍历完成时，'res'中包含了从起始到每个位置的最小翻转次数，最后从中选择最小的值即可。