2380-二进制字符串重新安排顺序需要的时间

给你一个二进制字符串 s 。在一秒之中， 所有 子字符串 "01" 同时 被替换成 "10" 。这个过程持续进行到没有
"01" 存在。

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

示例 1：

**输入：** s = "0110101"
**输出：** 4
**解释：**
一秒后，s 变成 "1011010" 。
再过 1 秒后，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 \rightarrow 10 的替换看成是 1 向左移动。每一秒，如果 1 的左面是 0，则会向左移动一步。注意连续的 11 不能同时向左移动。

从左到右遍历字符串：

1. 如果 1 的左侧没有 0，则无需移动。

2. 如果 1 的左侧存在 cnt(cnt > 0) 个 0，则至少需要 cnt 秒来移动；同时，如果这个 1 的左侧还存在 1，那么它至少需要比左侧那个 1 多一秒才能到达最终位置。

   这是因为，当左侧的 1 刚到达最终位置的时刻，右侧的 1 一定不会移动到最终位置，而是至少与前面的 1 间隔一个 0，因为连续的 11 无法同时向左移动，从而无法同时到达最终位置。

其实也可以从后往前统计 0 向右移动的秒数，思路是一样的。

详细证明附在代码之后。

时间复杂度：O(n)，空间复杂度：O(1)。

[g1-python3]

class Solution:
    def secondsToRemoveOccurrences(self, s: str) -> int:
        res, cnt = 0, 0
        for c in s:
            if c == '0': cnt += 1
            elif cnt: res = max(res + 1, cnt)
        return res

[g1-c++]

class Solution {
public:
    int secondsToRemoveOccurrences(string s) {
        int res = 0;
        for(int i = 0, cnt = 0; i < s.size(); ++i) {
            if(s[i] == '0') ++cnt;
            else if(cnt > 0) res = max(res + 1, cnt);
        }
        return res;
    }
};

详细证明：

每个 1 向左移动的过程中，有两种情况：

• 在到达最终位置之前，未受到左侧的 1 的 “阻挡”，也就是每一秒都移动了一次，此时，移动次数 = 其左侧 0 的个数；
• 在到达最终位置之前，受到了左侧 1 的 “阻挡”，也就是说，在某一时刻，其与左侧的 1 相邻而组成了 11。在此之后，我们可以证明，当左侧的那个 1 到达最终位置时，右侧的 1 一定与左侧的 1 间隔 1 个 0。此时，移动次数 = 左侧 1 的移动次数 + 1。

上面结论的证明：

• 当两个 1 相邻时，若左侧的 1 可以移动，此时右侧的 1 不可以移动，因此会有 11\rightarrow101；
• 当两个 1 间隔 1 个 0 时，也就是 101，那么当左侧的 1 可以移动时，右侧的 1 也可以移动，因此 101 继续保持一个 0 的间隔；当左侧的 1 不能移动时，右侧的 1 可以移动，此时两者又相邻了，成为 11。
• 综上所述，这两个 1 移动时，其间隔不会超过 1 个 0，但是当左侧的 1 刚到达最终位置时，两者又不可能相邻，因此，两者必定间隔 1 个 0。