最长有效括号
题目描述
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”
示例 2:
输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”
思路
用栈来做，将左括号的下标存储到栈中
当遇到右括号时判断，如果当前栈为空，则修改开头结点坐标
如果非空，弹出栈顶，再次判断栈是否为空，若为空，则比较开头结点到当前坐标长度是否是最大值
若非空，比较当前栈顶元素到当前结点到距离
Java实现
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<Integer>();
int ans=0;
int start=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='('){
stack.push(i);
}else{
if (stack.isEmpty()){
start=i+1;
continue;
}
else{
stack.pop();
if(stack.isEmpty()){
ans=Math.max(ans,i-start+1);
}
else{
ans=Math.max(ans,i-stack.peek());
}
}
}
}
return ans;
}
执行用时 :16 ms, 在所有 Java 提交中击败了29.59%的用户
内存消耗 :37.1 MB, 在所有 Java 提交中击败了84.71%的用户
