[LeetCode] 每日一题 2712. 使所有字符相等的最小成本（贪心算法）

题目链接

https://leetcode.cn/problems/minimum-cost-to-make-all-characters-equal

题目描述

给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作：

• 选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。

• 选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。

返回使字符串内所有字符 相等 需要的 最小成本 。

反转 字符意味着：如果原来的值是 '0' ，则反转后值变为 '1' ，反之亦然。

示例输入

示例 1

输入：s = "0011"
输出：2
解释：执行第二种操作，选中下标 i = 2 ，可以得到 s = "0000" ，成本为 2 。可以证明 2 是使所有字符相等的最小成本。

示例 2

输入：s = "010101"
输出：9
解释：执行第一种操作，选中下标 i = 2 ，可以得到 s = "101101" ，成本为 3 。
执行第一种操作，选中下标 i = 1 ，可以得到 s = "011101" ，成本为 2 。
执行第一种操作，选中下标 i = 0 ，可以得到 s = "111101" ，成本为 1 。
执行第二种操作，选中下标 i = 4 ，可以得到 s = "111110" ，成本为 2 。
执行第二种操作，选中下标 i = 5 ，可以得到 s = "111111" ，成本为 1 。
使所有字符相等的总成本等于 9 。可以证明 9 是使所有字符相等的最小成本。 

提示

• 1 <= s.length == n <= 10^5

• s[i] 为 '0' 或 '1'

解题思路

这道题的目标是让二进制字符串 s 中的所有字符相等，并且在反转操作的成本最小的情况下完成。最直观的想法是 模拟操作，但这样效率较低。幸运的是，我们可以利用 贪心算法 优化计算

核心观察

• 反转某一段字符，不会改变该段内部的相等关系

• 唯一会受到影响的是 该段的起点或终点字符与相邻字符的关系

• 因此，每当遇到相邻字符不同 (s[i] != s[i-1])，我们必须进行某种反转操作，使其相等

贪心策略

1. 遍历字符串，找出所有相邻字符不相等的位置

2. 计算最小的翻转成本：

   • 如果在 i 处字符不同，可以选择：

     • 反转 0 ~ i，成本为 i + 1

     • 反转 i ~ n-1，成本为 n - i

   • 选择较小的那个成本，累加到最终结果中

这个思路保证了最小的翻转成本，因为每次遇到不同的地方，我们都用最优的方式修正它，使得字符串变得更趋于一致

代码实现

class Solution {
    public long minimumCost(String s) {
        int n = s.length();
        long ans = 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                ans += Math.min(i, n - i);
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度： O(n) 🚀

  • 只需要遍历一次字符串，计算相邻不同字符的位置，所有操作均为 O(1)，整体复杂度 O(n)

• 空间复杂度： O(1) 🏎️

  • 只用了一个 long 变量 ans 存储答案，没有额外的空间开销，属于 原地计算

总结

这道题乍一看像是需要暴力模拟，但 贪心算法 提供了更优解法。核心思想是 关注相邻字符的变化点，在每个变化点使用最小成本的翻转策略，使得整个字符串最终变得一致。这样，我们在 O(n) 时间复杂度内 轻松完成求解，避免了不必要的计算✨

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。