0926. Flip String to Monotone Increasing

题目信息

题号:

0926

难度:

Medium

主题:

二进制字符串、单调结构、最少翻转

原题:

LeetCode 0926

重点:

一次操作翻转一个字符;目标字符串必须形如若干个 0 后接若干个 1,其中任一部分都允许为空

题目重述

给定二进制字符串 s。一次操作可以选择任意下标,把该位置的 0 改为 1,或把 1 改为 0。

若字符串中不存在某个 1 位于某个更靠后的 0 之前,则它单调递增;等价地,它可以表示为 0...01...1,全为 0 或全为 1 也合法。请返回把 s 变成单调递增字符串所需的最少翻转次数。

1 <= s.length <= 10^5。

自建示例

把中间的零翻为一:

输入:s = "0010101"
输出:2
解释:翻转下标 3 和 5 的两个 0,可得到 "0011111"。一次翻转无法消除原字符串中的两个下降位置,因此最少为 2。

字符串已经单调递增:

输入:s = "000111"
输出:0
解释:所有 0 都位于所有 1 之前,原字符串已经满足单调递增定义。