牛客编程巅峰赛S2第7场 - 钻石&王者 A题题解_小白的做题记录

做完题之后讲解了一个双指针的方法（O(N)）， 万分受教

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param x string字符串 
     * @return int整型
     */
    int Maximumlength(string x) {
        int n = x.size(), ans = 0;
        vector<int> a, c, b(n+1);
        for(int i = 0; i < n; ++i){
            b[i+1] = b[i];
            switch(x[i]){
            case 'a':
                a.emplace_back(i);
                break;
            case 'b':
                ++b[i+1];
                break;
            case 'c':
                c.emplace_back(i);
            }
        }
        reverse(c.begin(), c.end());
        for(int i = 0, l = min(c.size(), a.size()); i < l; ++i, ++ans)
            if(c[i] < a[i] || b[c[i] + 1] - b[a[i]] < i + 1) break; //c 跑到了 a 的后面 或者 B的数量不足了
        return ans*3;
    }
};

------------------------手动分割线----------------------------
二分法：

两种二分的写法
左闭右开

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param x string字符串 
     * @return int整型
     */
    int Maximumlength(string x) {// 二分法
        int l = 0, r = (x.size()/3) + 1, len = x.size();
        while(l < r){
            int m = (l + r) >> 1, a = m, b = m, c = m;
            for(int i = 0; i < len; ++i){
                if(a>0){
                    if(x[i] =='a') --a;
                }
                else if(b>0){
                    if(x[i] =='b') --b;
                }
                else if(c>0){
                    if(x[i] =='c') --c;
                }
                else  break;
            }
            if(a +b +c > 0) r = m;
            else l = m + 1;
        }
        return (r-1)*3;
    }
};

左闭右闭

class Solution {
public:
    int Maximumlength(string x) {
        int l = 0, r = x.size()/3 , len = x.size(); // 二分法
        while(l <= r){
            int m = (l + r) >> 1, a = m, b = m, c = m;
            for(int i = 0; i < len; ++i){
                if(a>0){
                    if(x[i] =='a') --a;
                }
                else if(b>0){
                    if(x[i] =='b') --b;
                }
                else if(c>0){
                    if(x[i] =='c') --c;
                }
                else  break;
            }
            if(a +b +c > 0) r = m - 1;
            else l = m + 1;
        }
        return (r)*3;
    }
}；