二进制取反

题意

给定一个形如直方图的矩形列，求其中最大的矩形

方法

枚举范围(TLE)

分析

我们直接枚举所有取反的范围

对这个范围取反并比较，记录最大字典序的字符串

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串
     */
    string maxLexicographical(string num) {
        auto ans = num;
        for(int i = 0;i < num.size();i++){ // 翻转起始
            auto revnum = num;
            for(int j = i;j<num.size();j++){ // 翻转结束位置
                revnum[j] =  '0' + ((revnum[j] - '0')^1);
                if(revnum > ans) // 比较大小
                    ans = revnum;
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 先选左侧点，再选右侧点，每次翻转和比较，所以总时间复杂度为$O(n^3)O(n^3)$

空间复杂度: 只用了一个和原字符串等长的额外变量，所以空间复杂度为$O(n)O(n)$

贪心

分析

字典序是从左向右比，而字符串只包含0和1

所以把0变成1会变小，而把1变成0会变大

所以从左开始的一串零变成1，就是最大的字符串

样例

以题目样例数据1000为例

所以最后输出1111即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串
     */
    string maxLexicographical(string num) {
        auto ans = num;
        for(int i = 0;i < num.size();i++){
            if(ans[i] == '0'){ // 首个零
                for(int j = i;j < num.size();j++){ // 连续的一串
                    if(ans[j] == '1')break;
                    ans[j] = '1';
                }
                break;
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 因为个字符处理代价为常数，所以时间复杂度为$O(n)O(n)$

空间复杂度: 只用了一个和原字符串等长的额外变量，所以空间复杂度为$O(n)O(n)$