算法竞赛备考冲刺必刷题（C++） | 洛谷 P10472 括号画家

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P10472 括号画家 - 洛谷 (luogu.com.cn)

【题目描述】

Candela 是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。这一天，刚刚起床的 Candela 画了一排括号序列，其中包含小括号()、中括号[]和大括号{}，总长度为N NN。这排随意绘制的括号序列显得杂乱无章，于是 Candela 定义了什么样的括号序列是美观的：

1. 空的括号序列是美观的；
2. 若括号序列 A 是美观的，则括号序列(A)、[A]、{A}也是美观的；
3. 若括号序列 A、B 都是美观的，则括号序列AB也是美观的；

例如[(){}]()是美观的括号序列，而)({)[}](则不是。

现在 Candela 想在她绘制的括号序列中，找出其中连续的一段，满足这段子序列是美观的，并且长度尽量大。你能帮帮她吗？

【输入】

第一行一个长度为N NN的括号序列。

【输出】

一个整数，表示最长的美观的连续子序列的长度。

【输入样例】

({({(({()}})}{())})})[){{{([)()((()]]}])[{)]}{[}{)

【输出样例】

4

【算法标签】

《洛谷 P10472 括号画家》 #栈# #O2优化#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;string s;// 输入的括号字符串intmaxx;// 最长有效括号子串的长度intmain(){cin>>s;// 读入字符串// 遍历所有可能的子串起点for(inti=0;i<s.size()-1;i++){stack<char>sta;// 用于括号匹配的栈// 遍历以i为起点的所有子串for(intj=i;j<s.size();j++){// 如果是左括号，入栈if(s[j]=='('||s[j]=='['||s[j]=='{')sta.push(s[j]);// 如果是右小括号elseif(s[j]==')'){// 如果栈为空或栈顶不匹配，这个子串无效if(sta.size()==0||sta.top()!='(')break;// 结束当前子串检查elsesta.pop();// 匹配成功，弹出栈顶}// 如果是右中括号elseif(s[j]==']'){if(sta.size()==0||sta.top()!='[')break;elsesta.pop();}// 如果是右大括号elseif(s[j]=='}'){if(sta.size()==0||sta.top()!='{')break;elsesta.pop();}// 如果栈为空，说明当前子串是有效括号子串if(sta.size()==0)maxx=max(maxx,j-i+1);// 更新最大长度}}cout<<maxx<<endl;// 输出最长有效括号子串的长度return0;}

【运行结果】

({({(({()}})}{())})})[){{{([)()((()]]}])[{)]}{[}{) 4