题目

如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，

那么该字符串是 单调递增 的。

我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

返回使 s 单调递增 的最小翻转次数。

示例 1：输入：s = "00110" 输出：1

解释：我们翻转最后一位得到 00111.

示例 2：输入：s = "010110" 输出：2

解释：我们翻转得到 011111，或者是 000111。

示例 3：输入：s = "00011000" 输出：2

解释：我们翻转得到 00000000。

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

s 中只包含字符 '0' 和 '1'

注意：本题与主站 926 题相同：

解题思路分析

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题目，题目同leetcode 926.将字符串翻转到单调递增