Medium

题目描述

给你一个二进制字符串 s。在一秒钟内，所有出现的 "01" 都会同时被替换为 "10"。这个过程会重复，直到不再存在 "01" 的出现。

返回完成这个过程所需的秒数。

示例 1：

输入：s = "0110101"
输出：4
解释：
一秒后，s 变为 "1011010"。
再过一秒，s 变为 "1101100"。
第三秒后，s 变为 "1110100"。
第四秒后，s 变为 "1111000"。
不再存在 "01" 的出现，该过程用了 4 秒完成，所以返回 4。

示例 2：

输入：s = "11100"
输出：0
解释：
s 中不存在 "01" 的出现，该过程用了 0 秒完成，所以返回 0。

约束条件：

  • 1 <= s.length <= 1000
  • s[i] 是 '0' 或 '1'

**进阶：**你能在 O(n) 时间复杂度内解决这个问题吗？

解题思路

这道题有两种主要思路：

方法一：模拟法 直接按照题目描述进行模拟。每次遍历字符串，找到所有 “01” 模式并同时替换为 “10”，记录操作次数。重复此过程直到不再有 “01” 出现。

方法二：贪心法（推荐） 观察规律可以发现，每个 ‘0’ 需要向右移动，直到它右边没有 ‘1’ 为止。关键洞察是：每个 ‘0’ 最终移动的距离等于它右边 ‘1’ 的个数。而移动时间取决于路径上遇到的阻碍。

具体来说，从右往左遍历字符串：

  • 如果当前字符是 ‘1’，计数器 ones 加 1
  • 如果当前字符是 ‘0’ 且右边有 ‘1’（ones > 0），那么这个 ‘0’ 需要移动
  • 第一个需要移动的 ‘0’ 需要 ones 秒
  • 后续的 ‘0’ 除了要越过右边的 ‘1’，还要等前面的 ‘0’ 先移动，时间会累积

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int secondsToRemoveOccurrences(string s) {
        int time = 0;
        int ones = 0;
        
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] == '1') {
                ones++;
            } else if (ones > 0) {
                time = max(time + 1, ones);
            }
        }
        
        return time;
    }
};

class Solution:
    def secondsToRemoveOccurrences(self, s: str) -> int:
        time = 0
        ones = 0
        
        for i in range(len(s) - 1, -1, -1):
            if s[i] == '1':
                ones += 1
            elif ones > 0:
                time = max(time + 1, ones)
        
        return time

public class Solution {
    public int SecondsToRemoveOccurrences(string s) {
        int time = 0;
        int ones = 0;
        
        for (int i = s.Length - 1; i >= 0; i--) {
            if (s[i] == '1') {
                ones++;
            } else if (ones > 0) {
                time = Math.Max(time + 1, ones);
            }
        }
        
        return time;
    }
}

var secondsToRemoveOccurrences = function(s) {
    let time = 0;
    let ones = 0;
    
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
贪心法O(n)O(1)
模拟法O(n²)O(n)

相关题目