题目描述

一个由0和1构成的字符串，如果所有的0在所有的1前面，则我们说它是单调递增的。

给定一个由0和1构成的字符串S，我们可以将任何0变成1，或者1变成0。

请返回最小需要操作多少次，可以使S变成单调递增的。

注意：

1. 1 <= S.length <= 20000
2. S仅由'0'和'1'构成。

样例1

输入："00110"
输出：1
解释：可以将最后一位变成1，得到 00111。

样例2

输入："010110"
输出：2
解释：可以变成 011111, 或者变成 000111.

样例3

输入："00011000"
输入：2
解释：可以变成 00000000。

算法

(前缀和) $O(n)$

首先求出整个数组的前缀和，这样就可以用 $O(1)$ 的时间算出某一段中有多少个0和多少个1了。
例如，如果区间是[i, j]，前缀和是f[i]：

• 区间中1的个数是：f[j] - f[i - 1]；
• 区间中0的个数是总个数减去1的个数：(j - i + 1) - (f[j] - f[i - 1])；

然后从前往后依次枚举0和1的边界：

• 边界左边1的个数，就是左边需要进行操作的个数；
• 边界右边0的个数，就是右边需要进行操作的个数；

左右两边的和，就是该边界对应的总操作个数。遍历之后取个最小值即可。

时间复杂度分析：

• 求前缀和需要 $O(n)$ 的时间；
• 枚举边界需要 $O(n)$ 的时间；

所以总时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int n = S.size();
        vector<int> f(n + 1, 0);
        for (int i = 1; i <= n; i ++ ) f[i] = f[i - 1] + S[i - 1] - '0';
        int res = INT_MAX;
        for (int i = 1; i <= n; i ++ )
        {
            int left = f[i - 1];
            int right = (n - i + 1 - (f[n] - f[i - 1]));
            res = min(res, left + right);
        }
        res = min(res, f[n]);
        return res;
    }
};