题目 #
给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：
- 操作 1 ：如果二进制串包含子字符串
"00"，你可以用"10"将其替换。- 比方说，
"**00**010" -> "**10**010"
- 比方说，
- 操作 2 ：如果二进制串包含子字符串
"10"，你可以用"01"将其替换。- 比方说，
"000**10**" -> "000**01**"
- 比方说，
请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 **x **大于二进制字符串 **y **。
示例 1：
输入：binary = "000110"
输出："111011"
解释：一个可行的转换为：
"000110" -> "000101"
"000101" -> "100101"
"100101" -> "110101"
"110101" -> "110011"
"110011" -> "111011"示例 2：
输入：binary = "01"
输出："01"
解释："01" 没办法进行任何转换。解法 #
此题的数据量很大(10^5), 必须找到线性复杂度的方法才能解决。
我们从左往右地逐一处理，一开始我们只考虑前两个字符，然后逐步往尾部增加字符来考虑。分析情况之后，我们会发现，该问题的局部最优解即是全局最优解，即我们可以用贪心法来解决。
我们只需考虑尾部两个字符的情况：
- 00: 转换为 10
- 10: 如果前面还存在 0, 比如 xxx01110, 则我们可以通过连续转换(10->01)得到 xxx10111
- 11: 保持不变
- 01: 保持不变
由于字符串在 python 中是不可直接修改的，使用字符串拼接的开销也很大，我们可以用列表来存储字符，最后在将其拼接成字符串，但是可惜这个操作仍然会超时。
观察规律，我们会发现，由以上四种操作后，我们的结果字符串中最多只出现一个 0。因而我们唯一需要保存的就是这个 0 出现的位置。
还有一种直观的思维方式：
通过操作 10->01, 我们可以把所有的 1 都放到低位，所有的 0 都放到高位。
通过操作 00->10, 我们可以把高位连续的 00000 变成 11110
代码 #
class Solution:
def maximumBinaryString(self, binary: str) -> str:
if len(binary) < 2:
return binary
ans = [binary[0], binary[1]]
if ans == ['0', '0']:
ans = ['1', '0']
idx0 = 0 if ans[0] == '0' else -1
lastChr = ans[-1]
for i in range(2, len(binary)):
c = binary[i]
if lastChr + c == '01':
idx0 = i - 1
lastChr = '1'
elif lastChr + c == '00':
lastChr = '0'
elif lastChr + c == '10':
if idx0 > -1:
idx0 += 1
lastChr = '1'
else:
lastChr = '0'
else:
lastChr = '1'
return '1' * (len(binary) - 1) + lastChr if idx0 < 0 else '1' * idx0 + '0' + '1' * (len(binary) - idx0 - 1)