32.最长有效括号
32.最长有效括号
题解
题目：求匹配括号的最长长度
思路一 栈
遍历字符串 1.如果是(,则入栈 2.如果是),如果栈空，说明这个右括号是多于的，将对应的mark置1 如果栈不空，则弹出栈顶 3.遍历栈，如果栈里还有没有被弹出的(,将对应的mark置1 4.计算连续0的长度，即计算最长可用长度
思路二 dp
dp[i]表示以s[i]字符结尾的最长有效长度
如果s[i]== (
- 左括号不能与前面的元素匹配，所以dp[i]=0
如果s[i]== )
- 如果s[i-1]== (
- 说明构成了（）的形式，那么有效长度增加2，即dp[i]=dp[i-2]+2
- 如果s[i-1]== )
- 说明构成了xxx ))的形式，这个时候想要形成(())的形式，需要要求s[i-1]的位置是匹配的，如果s[i-1]不匹配，s[i]则不能与前面的(匹配
- 所以判断s[ i-1-dp[i-1] ] 是否为(
如果s[ i-1-dp[i-1] ]== ( ,说明 i-1-dp[i-1]的左括号和i的右括号匹配，则dp[i]=dp[i-2]+2
但是这里只是考虑了(())的情况，如果是()(())的情况呢？前面的()的长度我们也要加上,所以dp[i] = dp[i-1] + 2 + dp[i-2-dp[i-1]]
综上所述，dp的状态转移方程为
dp[i] = dp[i-2] + 2 //xxxx() dp[i] = dp[i-1] + 2 + dp[i-2-dp[i-1]] //()(())
思路三 贪心 遍历两次
我们知道有效括号代表这能够匹配，那么
- 遇到(,left++ 遇到) right++
- 如果left=right,说明匹配成功
- 如果left<right，这个情况的前面相等时的长度已经记录过了，直接将left和right置为0
- 但是(()这种情况，将没有答案
- 这个时候倒着再遍历一遍，将第三步改为如果left>right即可
代码
func longestValidParentheses(s string) int { mark := make([]int, len(s)) stack := make([]int, 0) for i, ch := range s { if ch == '(' { //如果是(，则入栈 stack = append(stack, i) } if ch == ')' { //如果是） if len(stack) == 0 { //如果是多余的)，说明该位置不可用 mark[i] = 1 } else { stack = stack[:len(stack)-1] //不是多余的，则弹出一个( } } } for _, idx := range stack { //还在栈里面没有被匹配的(,都不可用 mark[idx] = 1 } ans, temp := 0, 0 for i := 0; i < len(mark); i++ { //计算最长可用长度 if mark[i] == 1 { temp = 0 } else { temp++ ans = max(ans, temp) } } return ans } func max(i, j int) int { if i > j { return i } return j }
func longestValidParentheses(s string) int { ans := 0 dp := make([]int, len(s)) for i := 1; i < len(s); i++ { ch := s[i] if ch == '(' { dp[i] = 0 } else if ch == ')' { if s[i-1] == '(' { if i-2 >= 0 { dp[i] = dp[i-2] + 2 //xxxx() } else { dp[i] = 2 //() } } else if s[i-1] == ')' { if i-1-dp[i-1] >= 0 && s[i-1-dp[i-1]] == '(' { if i-2-dp[i-1] >= 0 { dp[i] = dp[i-1] + 2 + dp[i-2-dp[i-1]] //()(()) } else { dp[i] = dp[i-1] + 2 //(()) } } } } ans = max(ans, dp[i]) } return ans } func max(i, j int) int { if i > j { return i } return j }
func longestValidParentheses(s string) int { left, right := 0, 0 ans := 0 for _, v := range s { if v == '(' { left++ } else { right++ } if left == right { ans = max(ans, left+right) } if right > left { left, right = 0, 0 } } left, right = 0, 0 for i := len(s) - 1; i >= 0; i-- { v := s[i] if v == '(' { left++ } else { right++ } if left == right { ans = max(ans, left+right) } if left > right { left, right = 0, 0 } } return ans } func max(i, j int) int { if i > j { return i } return j }
