LeetCode LCR 092. 将字符串翻转到单调递增

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ LCR 092. 将字符串翻转到单调递增

思路分析

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

核心思路：

dp0 表示将前缀变成全 0 的最小翻转次数，dp1 表示前缀变成单调递增的最小翻转次数。

遍历每个字符，根据是否为 0/1 更新 dp0 与 dp1。

最终答案为 min(dp0, dp1)，因为全 0 也满足单调递增。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)。

class Solution {
    public int minFlipsMonoIncr(String s) {
        int dp0 = 0;
        int dp1 = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int newDp0 = dp0 + (c == '1' ? 1 : 0);
            int newDp1 = Math.min(dp0, dp1) + (c == '0' ? 1 : 0);
            dp0 = newDp0;
            dp1 = newDp1;
        }

        return Math.min(dp0, dp1);
    }
}

func minFlipsMonoIncr(s string) int {
    dp0, dp1 := 0, 0
    for i := 0; i < len(s); i++ {
        c := s[i]
        newDp0 := dp0
        if c == '1' {
            newDp0 = dp0 + 1
        }
        newDp1 := dp0
        if dp1 < newDp1 {
            newDp1 = dp1
        }
        if c == '0' {
            newDp1++
        }
        dp0, dp1 = newDp0, newDp1
    }
    if dp0 < dp1 {
        return dp0
    }
    return dp1
}

相似题目

题目	难度	考察点
1653. 使字符串平衡的最少删除次数	中等	动态规划
121. 买卖股票的最佳时机	简单	状态优化
714. 买卖股票的最佳时机含手续费	中等	状态机
309. 最佳买卖股票时机含冷冻期	中等	动态规划
188. 买卖股票的最佳时机 IV	困难	状态压缩

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/88719098