最长合法括号子串

题目 最长合法括号子串

image-0d7480ad

思路分析

上题的简化

思路见 括号画家

多了一个计数 如果最长为6 然后有两条是6的 要把这个2记录下来

那就用一个temp把每轮的值存一下

与之前保存的最大答案比一下

如果更大 就更新

如过不是一开始的情况（0）且temp与最大答案相同

就cnt++

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef pair<char,int> PCI;

string s;

int main()

{

    cin>>s;

    stack<PCI> stk;

    int idx=0;

    int ans=0,cnt=1;

    stk.push({'0',0});

    for(auto c:s){

        ++idx;

        if(stk.size() && (stk.top().first=='(' && c==')'))

            stk.pop();

        else

            stk.push({c,idx});

        int temp=idx-stk.top().second;

        if(temp>ans)

            ans=temp,cnt=1;

        else if(temp>0 && temp==ans)

            cnt++;

    }

    cout<<ans<<" "<<cnt<<endl;

    return 0;

}

同类题型

视频讲解

⬅️ 插松枝 🏠 00-刷题理模型 ➡️ 栈的压入、弹出序列