# Flip String to Monotone Increasing

<https://leetcode.com/problems/flip-string-to-monotone-increasing/>

> We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.
>
> Return the minimum number of flips to make S monotone increasing.
>
> Example 1:
>
> Input: "00110"
>
> Output: 1
>
> Explanation: We flip the last digit to get 00111.
>
> Example 2:
>
> Input: "010110"
>
> Output: 2
>
> Explanation: We flip to get 011111, or alternatively 000111.
>
> Example 3:
>
> Input: "00011000"
>
> Output: 2
>
> Explanation: We flip to get 00000000.
>
> Note:
>
> 1 <= S.length <= 20000
>
> S only consists of '0' and '1' characters.

## Thoughts

单调增只能是00…11…。因此是从某位开始后面都是1时需要翻转(0和1值对调)次数最少即答案。 可以用类似dp的思想，让f(i)表示前i个数组元素维持单调增需要的最少翻转次数。假设我们要翻转的是1之后的0，观察到当1之后0数目大于1的数目时，此时把前面的1翻转成0次数要更小。这个性质在数组任何位置都正确。比如0010011000，当到了第一个1后面的第二个0时，应当把第一个1翻成0，这样当前子数组还是单调增的，因此f(4) = 2。剩下的11000同理，经过f(6) = f(5) = f(4), f(7) = f(4) + 1(翻转第一个0为1)， f(8) = f(7) + 1 (翻转第二个0)，但f(9)此时1后面的0比1多，应当翻转前两个1，因此f(9) = f(4) + 2 = 4. f数组只是帮助理解，并不需要真的一个数组，只要两个变量分别记录当前位置时前面和现在的1个数，以及当前位置应当翻转的个数（默认为1后0的个数，当超过1的个数时，替换成1的个数）。

## Code

```
class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int flips = 0, ones = 0;
        for (int i = 0; i < S.size(); ++i) {
            if (S[i] == '0') {
                if (ones == 0) continue;
                ++flips;
            } else {
                ++ones;
            }
            if (flips > ones) flips = ones;
        }
        return flips;
    }
};
```

## Analysis

TC：O(N), OC: O(1).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/array_and_numbers/flip-string-to-monotone-increasing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.