LeetCode 补充题 177. 单次区间翻转后的最大二进制字符串
题目描述
牛客原题： ✅ 补充题 177. 单次区间翻转后的最大二进制字符串
给定只含
0、1的字符串s，至多翻转一个连续区间中的全部比特，使结果的字典序最大。
示例 1：
输入：
s = "1001"
输出："1111"
解释： 翻转下标1…2的两个 0，得到最大字典序字符串。
示例 2：
输入：
s = "111"
输出："111"
解释： 允许不执行翻转，任何翻转都会使字典序变小。
提示：
- 字符串只含
0、1。 - 至多选择一个连续区间翻转，也可以不操作。
题意分析
等长二进制串的字典序由第一个不同位决定，越靠左的改善优先级越高。一次连续翻转会同时把 0 变 1、1 变 0，因此要确定最早该改善的位置，以及何时继续会造成更早的损失。
解法：从第一个零开始翻转连续零段
核心思路
[!blue]
翻转不能从原串的 1 开始，否则第一个变化位变为 0，结果更小。有 0 时应从最早的 0 开始，因为跳过它而只改善后面位置，必然不如将这一位变成 1。
从这里开始连续的 0 都可以翻成 1，延长到每一个后续零都会在尚未决定的最早位置改善结果。但遇到第一个 1 必须停止，越过它会先将它变为 0，后面再多的改善也无法补偿。
因而只翻转第一个连续零段。全部为 1 或输入为空时不操作；结果在字符缓冲区中构造，保留该段之外所有字符。
解题步骤
- 找到第一个 0；不存在则不翻转。
- 从该位置向右找到连续零段的终点。
- 只把这段零变为一，保留其后的所有字符。
代码实现
class Solution {
public String maximize(String s) {
char[] a = s.toCharArray();
int i = 0;
while (i < a.length && a[i] == '1') {
i++;
}
while (i < a.length && a[i] == '0') {
a[i++] = '1';
}
return new String(a);
}
}
func maximize(s string) string {
a := []byte(s)
i := 0
for i < len(a) && a[i] == '1' {
i++
}
for i < len(a) && a[i] == '0' {
a[i] = '1'
i++
}
return string(a)
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(n)$，用于结果缓冲区。
关键点总结
[!green]
最早的 0 变成 1 带来最大收益；若翻转越过随后的第一个 1，会在最高尚未决定的位置变差，所以应立即停止。
易错点总结
[!yellow]
只能翻转一个区间，不能把所有不相邻的0都变成1。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 670. 最大交换 | 中等 | 同样只有一次操作机会，字典序或数值最大化优先改善最高位；本题翻区间，原题交换两个位置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！