题目描述
给你一个 二进制字符串 s
。
你可以对这个字符串执行 任意次 下述操作:
- 选择字符串中的任一下标
i
(i + 1 < s.length
),该下标满足s[i] == '1'
且s[i + 1] == '0'
。 - 将字符
s[i]
向 右移 直到它到达字符串的末端或另一个'1'
。例如,对于s = "010010"
,如果我们选择i = 1
,结果字符串将会是s = "000110"
。
返回你能执行的 最大 操作次数。
样例
输入: s = "1001101"
输出: 4
解释:
可以执行以下操作:
选择下标 i = 0。结果字符串为 s = "0011101"。
选择下标 i = 4。结果字符串为 s = "0011011"。
选择下标 i = 3。结果字符串为 s = "0010111"。
选择下标 i = 2。结果字符串为 s = "0001111"。
输入: s = "00111"
输出: 0
限制
1 <= s.length <= 10^5
s[i]
为'0'
或'1'
。
算法
(贪心) $O(n)$
- 显然,先移动前面的
1
,可以得到更多的移动机会。这是因为移动时遇到后面的1
就会阻塞,如果后面的1
再次移动,则这个1
就额外获得了一次移动机会。 - 遍历字符串,如果遇到了
0
且上一个字符为1
,则可以移动上一组所有的1
各一次,直到遇到下一个1
或终点,然后新的1
与上一组的1
进行合并。 - 在遍历时,维护变量
buf
表示当前组内1
的个数。如果遇到了0
且上一个字符为1
,则答案增加buf
。如果遇到了1
,则buf
增加 1。
时间复杂度
- 遍历字符串一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int maxOperations(string s) {
const int n = s.size();
int ans = 0, buf = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '1')
++buf;
else if (i > 0 && s[i] == '0' && s[i - 1] == '1')
ans += buf;
}
return ans;
}
};