題目

如果一個由 '0' 和 '1' 組成的字串，

是以一些 '0'（可能沒有 '0'）後面跟著一些 '1'（也可能沒有 '1'）的形式組成的，那麼該字串是單調遞增的。

我們給出一個由字元 '0' 和 '1' 組成的字串 S，我們可以將任何 '0' 翻轉為 '1' 或者將 '1' 翻轉為 '0'。

返回使 S 單調遞增的最小翻轉次數。

示例 1：輸入："00110" 輸出：1

解釋：我們翻轉最後一位得到 00111.

示例 2：輸入："010110" 輸出：2

解釋：我們翻轉得到 011111，或者是 000111。

示例 3：輸入："00011000" 輸出：2

解釋：我們翻轉得到 00000000。

提示：1 <= S.length <= 20000

S 中只包含字元 '0' 和 '1'

解題思路分析

1、動態規劃；時間複雜度O(n)，空間複雜度O(n)

func minFlipsMonoIncr(S string) int {	n := len(S)	dpA := make([]int, n) // 0 結尾	dpB := make([]int, n) // 1 結尾	if S[0] == '1' {		dpA[0] = 1	} else {		dpB[0] = 1	}	for i := 1; i < n; i++ {		if S[i] == '1' {			dpA[i] = dpA[i-1] + 1            // 需要改為0			dpB[i] = min(dpB[i-1], dpA[i-1]) // 1結尾和0結尾的最小值		} else {			dpA[i] = dpA[i-1]                    // 不需要改為0			dpB[i] = min(dpB[i-1], dpA[i-1]) + 1 // 1結尾和0結尾的最小值+1		}	}	return min(dpA[n-1], dpB[n-1])}func min(a, b int) int {	if a > b {		return b	}	return a}

2、動態規劃；時間複雜度O(n)，空間複雜度O(1)

func minFlipsMonoIncr(S string) int {	n := len(S)	a := 0 // 0 結尾	b := 0 // 1 結尾	if S[0] == '1' {		a = 1	} else {		b = 1	}	for i := 1; i < n; i++ {		if S[i] == '1' {			a, b = a+1, min(a, b)		} else {			a, b = a, min(a, b)+1		}	}	return min(a, b)}func min(a, b int) int {	if a > b {		return b	}	return a}

3、字首和；時間複雜度O(n)，空間複雜度O(n)

func minFlipsMonoIncr(S string) int {	n := len(S)	arr := make([]int, n+1)	for i := 1; i <= n; i++ {		arr[i] = arr[i-1]		if S[i-1] == '1' {			arr[i]++		}	}	res := n	for i := 0; i <= n; i++ {		left := arr[i]		right := n - i - (arr[n] - arr[i])		res = min(res, left+right)	}	return res}func min(a, b int) int {	if a > b {		return b	}	return a}

總結

Medium題目，可以使用動態規劃，也可以使用字首和統計1的個數，然後遍歷計算左邊需要翻轉1的個數+右邊需要翻轉0的個數