926. 将字符串翻转到单调递增
题目：如果一个二进制字符串，是以一些 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 <= 105
s[i] 为 '0' 或 '1'
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/flip-string-to-monotone-increasing
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
首先，我们假设其中一个位置为0和1的分界线，那么分界线前面全部是0，后面全部是1。
其次，我们可以统计前面1的个数，后面0的个数，这些都是需要旋转的。
最后，我们找到一个位置，前面1的个数加上后面0的个数最小的位置，就是我们要找的分界点，这个点旋转的最少次数就是两个数的加和。
代码：
class Solution {
public:
int minFlipsMonoIncr(string s) {
int n = s.size();
vector zero(n + 1), one(n + 1);
for(int i = 1; i <= n; ++i) {
// [0, i - 1] 的 1 数量
one[i] = one[i - 1] + (s[i - 1] == '1');
}
for(int i = n - 1; i >= 0; --i) {
// [i, n - 1] 的 0 的数量
zero[i] = zero[i + 1] + (s[i] == '0');
}
int ret = n;
for(int i = 0; i < n; ++i) {
// i 位置为分界线，该位置是 0 或 1 无所谓
// [0, i - 1]的所有 1 翻转为 0， [i + 1, n - 1]的所有 0 翻转为 1
int cur = one[i] + zero[i + 1];
ret = min(ret, cur);
}
return ret;
}
};
