0926. Flip String to Monotone Increasing¶
题目信息¶
- 题号:
0926
- 难度:
Medium
- 主题:
二进制字符串、单调结构、最少翻转
- 原题:
- 重点:
一次操作翻转一个字符;目标字符串必须形如若干个
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 之前,原字符串已经满足单调递增定义。