问题描述
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
解题思路1
有效的括号字符串意味着每一个左括号 '(' 都可以找到一个相匹配的右括号 ')'。栈可以帮助我们追踪尚未匹配的括号，并有效地处理嵌套结构。
解题步骤如下：
- 初始化一个栈，并将一个特殊的索引 -1 压入栈。这一步是为了方便计算最长有效子串的长度。
- 遍历字符串的每个字符：
- 如果字符是 '('，将其索引压入栈。
- 如果字符是 ')'：
- 弹出栈顶元素（这代表最近的一个 '(' 已经被匹配）。
- 如果栈为空，说明没有 '(' 可以与当前的 ')' 匹配，将当前的索引压入栈作为新的起点。
- 如果栈不为空，当前索引减去栈顶元素索引即为有效子串的长度，更新最长有效长度。
- 返回最长有效长度。
代码实现：
class Solution {
public:
int longestValidParentheses(string s) {
int maxLength = 0;
stack<int> indexStack;
indexStack.push(-1); // 前一个没有匹配的 ')' 的位置
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
// 将 '(' 的索引入栈
indexStack.push(i);
} else {
// 弹出栈顶元素
indexStack.pop();
if (indexStack.empty()) {
// 如果栈为空，意味着没有 '(' 可以与当前 ')' 匹配
indexStack.push(i); // 当前位置变为最后一个没有匹配的 ')'
} else {
// 栈不为空，则计算有效长度
int validLength = i - indexStack.top();
maxLength = max(maxLength, validLength);
}
}
}
return maxLength;
}
};这个解题思路主要参考了逆波兰表示法这个知识点。
解题思路2
第二种方法效率更高，但思路没有上面第一种思路清晰。
使用两个计数器
我们采用两个计数器（left 和 right）来分别跟踪左括号和右括号的数量。这种方法的关键在于通过两次遍历字符串来确保所有的括号都能找到对应的匹配，从而计算出最长的有效括号子串。
第一次遍历：从左到右
在第一次遍历中，我们从字符串的开始到结束进行扫描：
- 遇到 '(' 时，增加
left计数器。 - 遇到 ')' 时，增加
right计数器。 - 每当
left和right数量相等时，我们更新最长有效子串的长度，这是因为到目前为止，所有遇到的括号都能完全匹配。 - 如果
right的数量超过left，这表明括号已经无法匹配，需要重置两个计数器。这是因为任何以 ')' 开始的子串都不可能是有效的。
第二次遍历：从右到左
第二次遍历与第一次遍历类似，但方向相反。这主要是为了捕捉那些在第一次遍历中由于左括号过多而未能正确处理的情况：
- 遇到 ')' 时，增加
right计数器。 - 遇到 '(' 时，增加
left计数器。 - 当
left和right数量相等时，同样更新最长有效子串的长度。 - 如果
left数量超过right，则重置两个计数器，因为任何以 '(' 结尾的子串都不能是有效的。
代码实现：
class Solution {
public:
int longestValidParentheses(string s) {
int left = 0, right = 0, maxLength = 0;
// 第一次遍历：从左到右
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxLength = max(maxLength, 2 * right);
} else if (right > left) {
left = 0;
right = 0;
}
}
left = 0;
right = 0;
// 第二次遍历：从右到左
for (int i = s.length() - 1; i >= 0; --i) {
if (s[i] == ')') {
right++;
} else {
left++;
}
if (left == right) {
maxLength = max(maxLength, 2 * left);
} else if (left > right) {
left = 0;
right = 0;
}
}
return maxLength;
}
};
