最长有效括号
今天，打开lectcode，无意间看到了这道题目，读了一遍，不出所料，不会写，最后看了看博客，终于搞懂了，必须记录一下心得。
一.题目描述
这道题目很简洁，就是要求我们获取最长有效的子字符串的长度。
二.讲解算法原理
本题的解决方法有些特殊，我们可以很自然的想到要用到栈结构，但入栈的不是字符串中的字符，而是字符串中字符的下标。
本题是通过维护一个记录各个括号位置的堆栈来实现的。即stack<int>,另外，通过一个变量start来记录有效括号的起始位置。
如果是左括号，那就入栈，有括号是不入栈的，这是我们解决括号问题的一贯思路，即栈中储存的是左括号的下标，没有有括号的下标，
如果是右括号，那就得分情况讨论了：
情况一：如果此时堆栈不为空，那么说明得到了一对括号。此时，将堆栈中的括号出栈，出栈之后，如果堆栈空了，那么可以得到最长有效括号的长度为max(max_len,i-start),如果不为空，那么当前的的最大长度为max(max_len,i-temp.top()),
情况二：如果此时堆栈为空：那么当前遇到的右括号必然是非法的，重置起始位置。
三.代码实现
class Solution {
public:
int longestValidParentheses(string s) {
int max_len = 0;
int start = -1;
if (s.empty()) return 0;
stack<int> temp;
for (int i = 0; i < s.size(); ++i)
{
if ('(' == s[i])
{
temp.push(i);
}
else // (( ))
{
if (!temp.empty())
{
int n = temp.top();
temp.pop();
if (temp.empty())
max_len = max(max_len, i - start);
else
max_len = max(max_len, i - n);
}
else
{
start = i;
}
}
}
return max_len;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-06-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
