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 <= 10^5
s[i] 为 ‘0’ 或 ‘1’

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/flip-string-to-monotone-increasing
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

考虑将第i位作为0和1的分界点，左边都是0，右边都是1，第i位是0还是1都可以。然后计算左边1的个数，右边0的个数，两者相加就是将第i位作为分界点所需的操作数cnt，最后返回min(cnt)。实现代码一。

代码

代码一

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        // zero[i]表示[i+1,n-1]中0的个数
        int[] zero = new int[n];
        // one[i]表示[0,i-1]中1的个数
        int[] one = new int[n];
        int cnt1 = 0;
        int cnt0 = 0;
        // 一次遍历计算one和zero数组
        for (int i = 0; i < n; i++) {
            one[i] = cnt1;
            cnt1 += s.charAt(i) - '0';
            zero[n - 1 - i] = cnt0;
            cnt0 += 1 - (s.charAt(n - 1 - i) - '0');
        }
        int ans = n;
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, one[i] + zero[i]);
        }
        return ans;
    }
}