来源:力扣(LeetCode)
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 1:
输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"
示例 2:
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"
示例 3:
输入:s = ""
输出:0
提示:
0 <= s.length <= 3 * 104
s[i]
为 '('
或 ')'
遍历字符串,准备一个栈,存放字符串下标,首先放入初始参照物-1,遇到'('入栈,遇到')'出栈,并且判断栈长度,如果不为空,更新最大合法字符串长度,否则将当前下标放入栈中
class Solution {
public int longestValidParentheses(String s) {
int res = 0;
int len = s.length();
Stack<Integer> stack = new Stack<>();
//先入栈-1作为参照物
stack.push(-1);
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
// 左括号的索引,下标入栈
if(c == '('){
stack.push(i);
}else{
// 遍历到右括号,栈顶的左括号被匹配,出栈
stack.pop();
// 栈空
if(stack.isEmpty()){
// 下标入栈
stack.push(i);
}else{
//栈未空, 计算有效连续长度
res = Math.max(res,i - stack.peek());
}
}
}
return res;
}
}
对于这种括号匹配问题,一般都是使用栈来解决,当然也有动态规划,不过思路没有栈清晰,容易绕进去。