文章

1

粉丝

0

获赞

1

访问

107

头像
最长的括号匹配 题解:
P5227 中国科学技术大学2024年机试题
发布于2025年7月23日 20:04
阅读数 107

  1. 栈的初始化:压入 -1 作为 “基准索引”(用于简化第一个有效子串的长度计算)。
  2. 遍历字符串
    • 遇到左括号 '(':将其索引压入栈(等待匹配)。
    • 遇到右括号 ')'
      • 先弹出栈顶元素(尝试匹配最近的左括号)。
      • 若弹出后栈为空:当前右括号无法匹配,将其索引压入栈作为 “新基准”。
      • 若弹出后栈非空:当前索引 - 栈顶索引 = 有效子串长度,更新最大长度。
#include <bits/stdc++.h>

using namespace std;

int main()
{
	string str;
	cin >> str;
	
	stack<int> st;
	st.push(-1);
	int maxlen = 0;
	
	//栈里只会压入左括号的索引或者作为基准点的特殊值 
	for(int i = 0; i < str.size(); i++)
	{
		//左括号的话 索引入栈 
		if(str[i] == '(')
		{
			st.push(i); 
		}	
		else
		{
			//如果是右括号 先弹出栈顶
			st.pop();
			if(st.empty())
			{
				//栈空 当前右括号无法匹配 作为新基准	
				st.push(i);
			}
			else
			{
				//栈非空 成功匹配
				 maxlen = max(maxlen, i - st.top());
			} 
		}
		
	} 
	cout << maxlen << endl;
	
	
	return 0;
 } 

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发