32. 最长有效括号

题目描述

32. 最长有效括号 - 力扣（LeetCode）

给你一个只包含'('和')'的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如"(()())"。

示例 1：

输入：s = "(()"输出：2解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"输出：4解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""输出：0

解题思路：

暴力解法：超出了时间限制

class Solution { public static int longestValidParentheses(String s) { if(s==null||s.length()<1){ return 0; } int res=0; for(int i=s.length()-1;i>0;i--){ if(s.charAt(i)==')'){ res=Math.max(res,curValid(s,i)); } if(res>=i){ break; } } return res; } public static int curValid(String s,int index){ if(index==0){ return 0; } Stack<Character> r_stack = new Stack<>();//")" int res = 0; r_stack.push(s.charAt(index)); int start =0; int n=index; while(start<=index-1){ while(index-1>=start){ index--; Character ch= s.charAt(index); if(ch==')'){ r_stack.push(ch); }else{ if(r_stack.isEmpty()){ return res; }else{ res+=2; r_stack.pop(); } } } if(!r_stack.isEmpty()){ start=start+r_stack.size(); r_stack.clear(); index=n; r_stack.push(s.charAt(index)); res = 0; }else{ break; } } return res; } }