leetcode 32 最长有效括号

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()”

示例 2:

输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”

解法一 动态规划

感觉动态规划很考验逻辑思维能力，没有什么固定的模板，状态转移方程逻辑性很强（这道题本菜鸡看题解的），本题代码量不多。在这里插入代码片

class Solution { public int longestValidParentheses(String s) { int length=s.length(); //if(s==null||s.length()==0) return 0; int[] dp=new int[length]; int max=0; for(int i=1;i<length;i++){ if(s.charAt(i)==')'){ if(s.charAt(i-1)=='('){ dp[i]=(i>1?dp[i-2]:0)+2; } else{ if(i-dp[i-1]-1>=0){ if(s.charAt(i-dp[i-1]-1)=='('){ dp[i]=(i-dp[i-1]-2>0?dp[i-dp[i-1]-2]:0)+dp[i-1]+2; } } } } max=Math.max(max,dp[i]); } return max; } }

看不明白的话找样例手动跑遍就容易理解了。

解法二 栈

此方法的难点是对右括号的处理，当匹配到右括号栈为空应当如何处理，官方题解解释的不够详细， 参考大佬的题解：大佬解释

public class Solution { public int longestValidParentheses(String s) { Deque<Integer> stack=new ArrayDeque<>(); int max=0; stack.addLast(-1); for(int i=0;i<s.length();i++){ if(s.charAt(i)=='('){ stack.addLast(i); } else{ stack.removeLast(); if(stack.isEmpty()){ stack.addLast(i); } else{ max=Math.max(max,i-stack.peekLast()); } } } return max; } }

附上链接 题目描述