Medium

题目描述

如果一个二进制字符串由若干个 0（可能没有）后面跟着若干个 1（也可能没有）组成，那么该字符串是单调递增的。

给你一个二进制字符串 s，你可以将 s[i] 从 ‘0’ 翻转为 ‘1’ 或者从 ‘1’ 翻转为 ‘0’。

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

示例 1：

输入：s = "00110"
输出：1
解释：翻转最后一位得到 00111。

示例 2：

输入：s = "010110"
输出：2
解释：翻转得到 011111，或者是 000111。

示例 3：

输入：s = "00011000"
输出：2
解释：翻转得到 00000000。

提示：

  • 1 <= s.length <= 10^5
  • s[i] 为 '0' 或 '1'

解题思路

这道题的核心思想是动态规划。要让字符串变成单调递增，意味着所有的0都在1的前面。

解法一：动态规划（推荐）

我们可以用两个变量来记录状态：

  • zeros：到当前位置为止，以0结尾的最小翻转次数
  • ones：到当前位置为止，以1结尾的最小翻转次数

对于每个位置的字符：

  • 如果是'0’：
    • 保持0不变，zeros不增加
    • 翻转为1，ones = min(ones, zeros) + 1
  • 如果是'1’：
    • 翻转为0，zeros++（因为破坏了单调性，所有之前的1都要变成0）
    • 保持1不变，ones = min(ones, zeros)

解法二：前缀和思想

另一种思路是枚举分割点，计算左边1的个数（需要翻转为0）加上右边0的个数（需要翻转为1）。

动态规划解法更优，时间复杂度O(n)，空间复杂度O(1)。

代码实现

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int zeros = 0, ones = 0;
        
        for (char c : s) {
            if (c == '0') {
                ones = min(ones, zeros) + 1;
            } else {
                ones = min(ones, zeros);
                zeros++;
            }
        }
        
        return min(zeros, ones);
    }
};

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        zeros = 0
        ones = 0
        
        for c in s:
            if c == '0':
                ones = min(ones, zeros) + 1
            else:
                ones = min(ones, zeros)
                zeros += 1
        
        return min(zeros, ones)

public class Solution {
    public int MinFlipsMonoIncr(string s) {
        int zeros = 0, ones = 0;
        
        foreach (char c in s) {
            if (c == '0') {
                ones = Math.Min(ones, zeros) + 1;
            } else {
                ones = Math.Min(ones, zeros);
                zeros++;
            }
        }
        
        return Math.Min(zeros, ones);
    }
}

var minFlipsMonoIncr = function(s) {
    let ones = 0;
    let flips = 0;
    
    for (let char of s) {
        if (char === '1') {
            ones++;
        } else {
            flips = Math.min(flips + 1, ones);
        }
    }
    
    return flips;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次
空间复杂度O(1)只使用常数个额外变量

相关题目