1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int minFlipsMonoIncr(String s) {
int[] postCount = new int[s.length()];
int zeroCount = 0;
for (int i = postCount.length - 1; i >= 0; i--) {
zeroCount += s.charAt(i) == '0' ? 1 : 0;
postCount[i] = zeroCount;
}
int minFlips = Integer.MAX_VALUE, flipToZeroCount = 0;
for (int i = 0; i < s.length(); i++) {
char letter = s.charAt(i);
minFlips = Math.min(minFlips, postCount[i] + flipToZeroCount);
if (letter == '1') {
flipToZeroCount += 1;
}
}
return Math.min(minFlips, flipToZeroCount);
}
}
|
我们假设从某个位置开始, 之后全是1(包括该位置). 那么我们需要从头开始往后遍历. 到达一个位置后, 我们需要知道把它之前的char全变为0需要多少flips, 把从自己到之后所有的char变为1需要多少flips, 加在一起就是从当前位置是1的mono increasing string的flips数目. 我们遍历完所有位置取最小. 同时不要忘了还可以所有的位置都是0. 因此再把这个情况和我们之前得到的最小值取小即可.
因此我们需要在每个位置之前1的个数以及之后(包括该位置)0的个数. 我们用一个postCount来记录各个位置之后(包括该位置)0的个数. 然后再从头开始往后遍历, 用一个变量记录当当前位置之前1的个数即可.
时间复杂度: O(n)
空间复杂度: O(n)
