括号画家

题目 括号画家

image-03ba00ac

思路分析

合理的对一定会被消除 至于是多长 我们可以用pair多存放一下每个元素的坐标

合理对的长度就是当前元素（被消除的最后一个右括号）减去当前栈首元素（最后一个没被消除的元素）的下标

防止边界情况 填一个哨兵位0

0 1 2 3 4 5 6 7

0 } { [ ( ) ] }

一定会消除成

0 1

0 }

那么长度就是 7-1=6

如果全消了

那长度也会是下标减去栈首的0 也满足

示例如下：

括号画家-2659c3aa

或者用遇到左括号加1 遇到右括号-1 若存在一对 则某一段的和必为0

代码实现

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
unordered_map<char,int> mp={
        {'{',-1},
        {'}',1},
        {'[',-2},
        {']',2},
        {'(',-3},
        {')',3},
    };
string s;

int main()
{
    cin>>s;
    stack<PII> stk;//一维存字符代码 二维存坐标
    int idx=0,ans=0;
    stk.push({0,0});
    for(auto c:s){
        ++idx;
        int t=mp[c];
        if(t<0)
            stk.push({t,idx});
        else if(t>0){
            if(stk.size() && stk.top().first==-t){
                stk.pop();
                if(stk.size())
                    ans=max(ans,idx-stk.top().second);
            }
            else
                stk.push({t,idx});
        }
    }
    cout<<ans<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 括号匹配 🏠 00-刷题理模型 ➡️ 括号的匹配