Description
給定一個只包含
'0'和'1'的字串s，你可以將任意字元翻轉（0 變 1 或 1 變 0）。回傳使字串變成單調遞增（所有 0 在所有 1 前面）的最少翻轉次數。
Example:
Input: s = “00110” Output: 1
Intuition#
遍歷時維護兩個狀態：到目前為止以 0 結尾和以 1 結尾的最少翻轉次數。
- 分割點思路：在某個位置之前全部是 0，之後全部是 1
- DP 思路：
dp0表示以 0 結尾的最少翻轉次數，dp1表示以 1 結尾的最少翻轉次數 - 若當前是 ‘0’：以 0 結尾不需翻轉，以 1 結尾需要翻轉
- 若當前是 ‘1’：以 0 結尾需要翻轉，以 1 結尾不需翻轉
Approaches#
1: 前綴和#
- 概念: 枚舉分割點，分割點左邊所有 1 要翻成 0，右邊所有 0 要翻成 1。用前綴和快速計算。
- 時間複雜度:
O(n) - 空間複雜度:
O(n)
class Solution {
fun minFlipsMonoIncr(s: String): Int {
val n = s.length
val ones = IntArray(n + 1) // ones[i] = s[0..i-1] 中 1 的數量
for (i in 0 until n) ones[i + 1] = ones[i] + (s[i] - '0')
var result = n
for (i in 0..n) {
val flipOnes = ones[i] // 左邊的 1 要翻成 0
val flipZeros = (n - i) - (ones[n] - ones[i]) // 右邊的 0 要翻成 1
result = minOf(result, flipOnes + flipZeros)
}
return result
}
}⭐2: 狀態 DP（空間 O(1)）#
- 概念: 維護
dp0（以 0 結尾的最少翻轉）和dp1（以 1 結尾的最少翻轉），逐字元更新。 - 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun minFlipsMonoIncr(s: String): Int {
var dp0 = 0 // 以 0 結尾的最少翻轉
var dp1 = 0 // 以 1 結尾的最少翻轉
for (c in s) {
if (c == '0') {
// dp0 不變（0 跟在 0 後面）
dp1 = minOf(dp0, dp1) + 1 // 把 0 翻成 1
} else {
dp1 = minOf(dp0, dp1) // 1 跟在 0 或 1 後面都可以
dp0 += 1 // 把 1 翻成 0
}
}
return minOf(dp0, dp1)
}
}🔑 Takeaways#
- Pattern: 狀態機 DP — 維護「以 0 結尾」和「以 1 結尾」兩個狀態的最優解
- 關鍵技巧: 前綴和和狀態 DP 是兩種等價的思路；狀態 DP 更簡潔且只需 O(1) 空間