LeetCode926:转换字符串至单调递增

在 LeetCode 926 题目中，我们面临的问题是如何通过最少的翻转次数将一个由 '0' 和 '1' 构成的字符串转换成单调递增的字符串。一个字符串被认为是单调递增的，如果它可以被描述为一段或零段 '0' 后跟随一段或零段 '1'。

给定一个字符串 S，我们的目标是确定最小的翻转次数以达到上述条件。翻转是指将字符串中的任意一个字符从 '0' 变为 '1' 或从 '1' 变为 '0'。

示例

示例 1:

输入: S = "00110"
输出: 1
解释: 我们可以通过翻转最后一个 '0' 来得到一个单调递增的字符串 "00111"。

示例 2:

输入: S = "010110"
输出: 2
解释: 我们可以通过翻转两个 '0' 来得到一个单调递增的字符串 "011111" 或 "000111"。

示例 3:

输入: S = "00011000"
输出: 2
解释: 我们可以通过翻转两个 '0' 来得到一个单调递增的字符串 "00000000"。

约束条件

• 1 <= S.length <= 20000


• S 仅包含 '0' 和 '1' 字符。

解决方案解析

为了将字符串 S 转换为单调递增，我们需要考虑两种基本策略：一是将所有 '1' 之前的 '0' 保持不变，之后的所有 '0' 翻转为 '1'；二是将所有 '1' 翻转为 '0'。在这两种策略中，选择翻转次数较少的一种即可。

具体实现时，可以使用动态规划的方法来计算每个位置 i 之前 '1' 的数量，以及从位置 i 开始到字符串末尾 '0' 的数量。这样，我们可以通过遍历字符串，计算出每种情况下的最小翻转次数，并最终确定全局最小值。

算法的时间复杂度为 O(n)，其中 n 是字符串 S 的长度，因为我们需要遍历整个字符串一次来计算所需的翻转次数。空间复杂度也为 O(n)，因为我们使用了一个额外的数组来存储每个位置之前 '1' 的累积数量。

代码示例

C++ 实现

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n = s.size();
        vector dp(n + 1);
        for (int i = 0; i             dp[i + 1] = dp[i] + (s[i] == '1');
        int result = dp[n];
        for (int i = 0; i             result = min(result, dp[i] + n - i - (dp[n] - dp[i]));
        return result;
    }
};

Python 实现

class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        prefix_sum = [0]
        for char in S:
            prefix_sum.append(prefix_sum[-1] + int(char))
        return min(prefix_sum[i] + len(S) - i - (prefix_sum[-1] - prefix_sum[i]) for i in range(len(prefix_sum)))