题目
给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
思路
判断有效的字符长度，很容易想到使用栈结构。 如果是“(”：则将左括号的下标推入栈中； 如果是“)”： 如果栈为空，证明此时右括号是非法的，将右括号的下标推入栈中，作为下一个有效括号的起点前一个坐标； 如果栈不为空，即有效括号的长度为栈弹出最上层栈中内容后，maxLen=Math.max(maxLen,i-stack.peek()).
代码
class Solution {
public int longestValidParentheses(String s
) {
int len
=s
.length();
Stack
<Integer> stack
=new Stack<>();
stack
.push(-1);
int maxLen
=0;
int tmp
=0;
for(int i
=0;i
<len
;i
++){
if(s
.charAt(i
)=='('){
stack
.push(i
);
}else{
stack
.pop();
if(stack
.isEmpty()){
stack
.push(i
);
}
maxLen
=Math
.max(maxLen
,i
-stack
.peek());
}
}
return maxLen
;
}
}
复杂度分析
时间复杂度：O(n)空间复杂度：O(n)
