题目主要信息

1、将一个二进制字符串num选择一个区间取反

2、获得最大的字典序

方法一：暴力法

具体方法

直接便利一遍，并记录出现0的位置，如果是连续位置的0，就将其变为1，由于要求最终的字典序最大，所以优先将前面连续的0变成1。

结合例子给出解释

0111001

虽然有两处连续的0，可以变成1111001 或者0111111 显然前者大于后者，所以优先取前面连续的0变成1.

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串
     */
    public String maxLexicographical (String num) {
        // write code here
        StringBuilder sb = new StringBuilder();
        int index = Integer.MIN_VALUE;//记录0的位置
        //开始遍历
        for(int i=0;i<num.length();i++){
            //是1 直接存
            if(num.charAt(i) == '1')
                sb.append('1');
            else{
                // 如果第一个为0 或者 连续为0的情况 或者中间某处开始为0
                if(i-index == 1 || i == 0 || index == Integer.MIN_VALUE){
                    sb.append('1');
                    index = i;
                }
                // 虽然是0 但是不满足上述的情况
                else
                    sb.append(num.charAt(i));
            }
        }
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$,需要遍历一次二进制字符串。
• 空间复杂度：$O(n)O(n)$，一个存储结果的StringBuilder，长度为字符串的长度。

方法二：C++代码

具体方法

方法和上面Java代码一样

C++

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串
     */
    public String maxLexicographical (String num) {
        // write code here
        StringBuilder sb = new StringBuilder();
        int index = Integer.MIN_VALUE;//记录0的位置
        //开始遍历
        for(int i=0;i<num.length();i++){
            //是1 直接存
            if(num.charAt(i) == '1')
                sb.append('1');
            else{
                // 如果第一个为0 或者 连续为0的情况 或者中间某处开始为0
                if(i-index == 1 || i == 0 || index == Integer.MIN_VALUE){
                    sb.append('1');
                    index = i;
                }
                // 虽然是0 但是不满足上述的情况
                else
                    sb.append(num.charAt(i));
            }
        }
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$,需要遍历一次二进制字符串。
• 空间复杂度：$O(n)O(n)$，一个存储结果的变量，长度为字符串的长度。