数大雁，ranges容器统计每只大雁叫声的开始索引和结束索引，q统计大雁开始叫q的索引，统计最大交集数即可

#include<bits/stdc++.h>
using namespace std;
int solution(string s)
{
    deque<int> q;
    int u=0;
    int a=0;
    int c=0;
    vector<vector<int>> ranges;//ranges统计的是多只大雁的叫声区间,开始索引，结束索引
    for(int i=0;i<s.size();i++)
    {
    switch(s[i])//遍历s
    {
    case 'q':
        q.push_back(i);//记录起始索引q的下标
    case 'u':
        if(u+1<=q.size())
            u++;
    case 'a':
        if(a+1<=u)
            a++;
    case 'c':
        if(c+1<=a)
            c++;
    case 'k':
        if(c>=1)
        {
            ranges.emplace_back(vector<int>{q.front(),i});//{}里有两个int数据，说明第二维数组下标只有0,1。
            //ranges[0][0]=q.front,ranges[0][1]=i
            q.pop_front();
            u--;
            a--;
            c--;
        }
        break;//进入下一轮扫描
    default:
        return -1;
    }

    }
    if(ranges.empty())
        return -1;
    int maxcount=1;
    //求最大交集
    for(int i=0;i<ranges.size();i++)//第i个点开始的索引，不断更新最大索引
    {
        int countt=1;
        for(int j=i+1;j<ranges.size();j++)//从这个点开始真正扫描取交集
        {
            if(ranges[i][1]>ranges[j][0])//上个点的结束索引大于上个点的开始索引，那么交集+1
                 {
                     countt++;
                 }
            maxcount=max(countt,maxcount);//每一轮后countt归1，每次更新最大交集数
        }
    }
    return maxcount;

}
using namespace std;
int main()
{
    string s;
    cin>>s;
    cout<<solution(s)<<endl;
    return 0;
}
 

原文地址：https://blog.csdn.net/m0_57195330/article/details/145245142

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！