[LeetCode]Flip String to Monotone Increasing

给定全是0和1组成的string，可以把0翻转成1或者1翻转成0，需要我们求最小的翻转次数可以使得string变成单调递增的序列。这道题我们枚举所有的可能即可，因为一旦某一位确定是1，那么之后的所有位均为1，所以我们需要枚举所有的位置计算最小值即可。我们用right[i]记录i位置右边包括自己有多少个0，然后左边扫的时候记录左边的1并计算结果。时间空间复杂度O(N)，代码如下:

	class Solution {
	public:
	int minFlipsMonoIncr(string S) {
	int len = S.size();
	//# of 0s in right, including self
	vector<int> right(len + 1, 0);
	int cnt = 0;
	for(int i = len - 1; i >= 0; --i)
	{
	if(S[i] == '0')++cnt;
	right[i] = cnt;
	}
	//cnt # of 1s in left
	cnt = 0;
	int res = INT_MAX;
	for(int i = 0; i < len + 1; ++i)
	{
	int curr = cnt + right[i];
	res = min(res, curr);
	if(S[i] == '1')++cnt;
	}
	return res;
	}
	};

view raw Flip String to Monotone Increasing.cpp hosted with ❤ by GitHub