---
title: "括号画家"
created: 2025-11-28
tags:
  - 算法
---

# 括号画家

## 题目 [括号画家](https://www.acwing.com/problem/content/152/)

![[image-03ba00ac.png]]

## 思路分析

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

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

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

0 1 2 3 4 5 6 7

0 } { [ ( ) ] }

一定会消除成

0 1

0 }

那么长度就是 7-1=6

如果全消了

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

示例如下：

![[括号画家-2659c3aa.gif]]

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


## 代码实现

```cpp
#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-刷题理模型]] ➡️ [[括号的匹配|括号的匹配]]