Medium

题目描述

桌子上有 n 个球，每个球的颜色不是黑色就是白色。

给你一个长度为 n 、下标从 0 开始的二进制字符串 s，其中 1 和 0 分别代表黑色和白色的球。

在每一步中，你可以选择两个相邻的球并交换它们。

返回「将所有黑色球都移到右侧，所有白色球都移到左侧」所需的 最小步数。

示例 1：

输入：s = "101"
输出：1
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "011"。
最初，1 没有全部在右侧，需要至少 1 步将它们移到右侧。

示例 2：

输入：s = "100"
输出：2
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "010"。
- 交换 s[1] 和 s[2]，s = "001"。
可以证明所需的最小步数为 2。

示例 3：

输入：s = "0111"
输出：0
解释：所有黑色球都已经在右侧了。

提示：

  • 1 <= n == s.length <= 10^5
  • s[i] 不是 '0' 就是 '1'

解题思路

解题思路

这是一个贪心算法问题。我们需要将所有的黑球（‘1’）移动到右侧，白球（‘0’）移动到左侧。

核心观察：

  • 由于只能交换相邻的球，每个黑球最终都需要"越过"它右侧的所有白球
  • 从右往左遍历字符串时，我们可以统计当前黑球需要越过多少个白球

算法步骤：

  1. 从右往左遍历字符串
  2. 维护一个计数器 zeros，记录当前位置右侧有多少个白球（‘0’）
  3. 当遇到黑球（‘1’）时，它需要与右侧所有白球进行交换，步数增加 zeros
  4. 当遇到白球（‘0’）时，将 zeros 计数器加1

为什么从右往左遍历？ 因为我们要将黑球移到最右侧，所以每个黑球需要知道它右侧有多少个白球需要越过。从右往左遍历可以很自然地统计这个信息。

时间复杂度：O(n)，只需要遍历一次字符串
空间复杂度：O(1)，只使用常数额外空间

代码实现

class Solution {
public:
    long long minimumSteps(string s) {
        long long steps = 0;
        int zeros = 0;
        
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] == '0') {
                zeros++;
            } else {
                steps += zeros;
            }
        }
        
        return steps;
    }
};

class Solution:
    def minimumSteps(self, s: str) -> int:
        steps = 0
        zeros = 0
        
        for i in range(len(s) - 1, -1, -1):
            if s[i] == '0':
                zeros += 1
            else:
                steps += zeros
        
        return steps

public class Solution {
    public long MinimumSteps(string s) {
        long steps = 0;
        int zeros = 0;
        
        for (int i = s.Length - 1; i >= 0; i--) {
            if (s[i] == '0') {
                zeros++;
            } else {
                steps += zeros;
            }
        }
        
        return steps;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var minimumSteps = function(s) {
    let steps = 0;
    let zeros = 0;
    
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历一次字符串，其中 n 是字符串长度
空间复杂度O(1)只使用常数额外空间存储计数器