难度: Medium
如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 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 <= 105s[i] 为 '0' 或 '1'运行时间: 64 ms
内存: 16.5 MB
class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
ans = count = 0
for c in s:
if c == '1':
count += 1
elif c == '0' and count > 0:
count -= 1
ans += 1
return ans
此题解采用一种贪心策略，通过计数器来监视已遍历的 '1' 的数量。对于每个 '0'，如果在此之前有 '1' 出现（即 count > 0），则将这个 '0' 翻转为 '1' 可以使得字符串趋向单调递增，同时将计数器减一表示减少一个需要翻转的 '1'，同时累加翻转次数。如果遇到 '1'，则增加计数器。这种方法实际上是在模拟将一部分 '1' 向前移动到所有的 '0' 之前，每次遇到 '0' 时，如果前面有 '1'，就考虑将前面的 '1' 翻转成 '0'，或者将当前的 '0' 翻转成 '1'，选择翻转 '0' 是因为这可以帮助维持后续的单调递增状态。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
ans = count = 0 # ans 记录最终需要的翻转次数，count 记录遇到的 '1' 的数量
for c in s:
if c == '1':
count += 1 # 如果字符是 '1'，增加 '1' 的计数
elif c == '0' and count > 0:
count -= 1 # 如果字符是 '0' 且前面有 '1'，则可以考虑翻转前面的 '1' 或当前的 '0'
ans += 1 # 增加翻转次数
return ans # 返回最小翻转次数
在处理字符串以使其单调递增时，直接翻转当前的'0'为'1'会简单地解决当前位置的问题，但不会减少后续可能需要的翻转次数。相反，通过翻转前面的'1'为'0'，我们实际上是在减少后续操作中可能需要的翻转次数，因为这样可以有效减少已经计数的'1'的数量，从而在后续遇到的'0'前有更少的'1'需要处理。这种方法更符合贪心策略的目标，即尽可能减少整体的翻转次数。
是的，维护的'1'的计数count实际上可以视为在当前点之前遇到的'1'的数量，这同样表示如果我们决定将所有后续的'0'都翻转为'1'，那么这些'1'就是当前需要翻转的最小数量。这个计数帮助我们决定在遇到'0'时是否需要翻转以及翻转哪些数字，以达到最小化总翻转次数的目的。
如果输入的字符串已是单调递增，算法的输出应该是0。在题解的算法中，当字符串已经是单调递增时，'1'的计数器将逐步增加，但不会有'0'出现在'1'之后，因此不会有翻转操作。所以，算法在这种情况下自然会输出0，无需额外修改。
在遇到连续的'0'时，算法不会重复计算翻转次数。以'00011000'为例，前三个'0'不会引发任何翻转操作，因为它们出现在任何'1'之前。当遇到'1'时，计数器开始增加。在处理最后三个'0'时，由于前面已记录两个'1'（'11'），每遇到一个'0'，都会将一个'1'的计数减去，并增加一个翻转次数。这样，后三个'0'会相应地减少两个'1'的计数，总共增加两次翻转操作。