Medium

题目描述

给你一个二进制字符串 s。

你可以对字符串执行以下操作任意次数：

  • 从字符串中选择任何索引 i，其中 i + 1 < s.length 且 s[i] == '1' 和 s[i + 1] == '0'。
  • 将字符 s[i] 向右移动，直到它到达字符串的末尾或另一个 '1'。例如，对于 s = "010010"，如果我们选择 i = 1，结果字符串将是 s = "000110"。

返回你可以执行的最大操作数。

示例 1：

输入：s = "1001101"
输出：4
解释：
我们可以执行以下操作：
- 选择索引 i = 0。结果字符串是 s = "0011101"。
- 选择索引 i = 4。结果字符串是 s = "0011011"。
- 选择索引 i = 3。结果字符串是 s = "0010111"。
- 选择索引 i = 2。结果字符串是 s = "0001111"。

示例 2：

输入：s = "00111"
输出：0

约束条件：

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

提示：

  • 每次选择最低可能的索引执行操作是最优的。
  • 从左到右遍历字符串，每当可能时就执行操作。

解题思路

这道题的关键是理解操作规则和找到最优策略。

核心思路：

  1. 我们需要找到所有可以移动的 '1'，即后面紧跟着 '0' 的 '1'
  2. 每次操作都会将一个 '1' 向右移动到下一个 '1' 的位置或字符串末尾
  3. 关键观察：每个 '1' 最终都会移动到字符串的末尾部分，形成连续的 '1'

贪心策略：

  • 从左到右遍历字符串
  • 对于每个可以移动的 '1'（即 s[i] == '1' 且 s[i+1] == '0'），我们计算它需要移动多少次
  • 每个这样的 '1' 贡献的操作数等于它右边的 '0' 的数量（因为每次移动都会跨过一个 '0'）

算法步骤：

  1. 从左到右遍历字符串
  2. 统计遇到的 '0' 的数量
  3. 当遇到 '1' 时，将当前的 '0' 计数加到总操作数中
  4. 这样每个 '1' 都会贡献它右边所有 '0' 的数量作为操作次数

时间复杂度 O(n)，空间复杂度 O(1)，这是最优解法。

代码实现

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

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

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

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

复杂度分析

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