Skip to content

Latest commit

 

History

History
101 lines (91 loc) · 3.71 KB

32.最长有效括号.md

File metadata and controls

101 lines (91 loc) · 3.71 KB
Raw

32.最长有效括号

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

  示例 1：

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

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

输入：s = ""
输出：0

方法一（栈）

  • 用栈来找出所有匹配的左右括号，并用一个列表来记录匹配括号的索引。
  • 于是这个列表中最长连续子序列的长度就是最长有效括号的长度。
public int longestValidParentheses(String s) {
    Stack<Integer> stack = new Stack<>();
    List<Integer> indexList = new LinkedList<>();
    for(int i = 0; i < s.length(); i++){
        if(s.charAt(i) == '(')
            stack.push(i);
        else{
            if(!stack.isEmpty()){
                indexList.add(stack.pop());
                indexList.add(i);
            }
        }
    }
    if(indexList.size() == 0)
        return 0;
    //寻找列表中最长连续子序列的长度
    Collections.sort(indexList);
    int max = 0;
    int index = 0;
    while(index < indexList.size() - 1){
        int count = 1;
        while(index < indexList.size() - 1 && indexList.get(index) == indexList.get(index + 1) - 1){
            count++;
            index++;
        }
        max = Math.max(count, max);
        index++;
    }
    return max;
}
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(n) 栈和列表所需的额外空间

方法二（动态规划）

1.定义状态

定义dp[i]为以位置i结尾的最长有效括号的长度

2.Base Case

  • 一个单括号不可能形成有效括号，因此dp[0] = 0
  • 如果1位置为右括号，0位置为左括号，那么dp[1] = 2

3.状态转移

  • 如果i位置为左括号，那么没有以这个位置结尾的有效括号，dp[i] = 0
  • 如果i位置为右括号，分两种情况：

    • 如果i-1位置为左括号，那么i-1位置和i位置能组成一个长度为2的有效括号，再加上以i-2位置结尾的最长有效括号的长度，即为以i位置结尾的最长有小括号的长度。dp[i] = dp[i-2] + 2

    • 如果i-1位置为右括号，那么以它结尾可能会有一定长度的有效括号，我们先越过这些位置，来到这些匹配好的有效括号前面一个位置，如果这个位置是左括号，那么dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]

      例如："())(())"，对于位置5，其前面的位置4已经有长度为2的匹配好的有效括号"()"，并且它们前面的位置2为左括号，可以与位置5的右括号匹配，因此dp[i]肯定能在dp[i-1]的位置上加2。但如例子所示，以位置1结尾还有长度为2的有小括号，与之后的有小括号连上了，这时我们就需要把这部分有效括号的长度dp[i - dp[i - 1] - 2]也加上。

public int longestValidParentheses(String s) {
    if(s == null || s.length() < 2)
        return 0;
    int[] dp = new int[s.length()];
    //Base Case
    dp[0] = 0;
    dp[1] = s.charAt(1) == ')' && s.charAt(0) == '(' ? 2 : 0;
    int max = Math.max(dp[0], dp[1]);
    for(int i = 2; i < s.length(); i++){
        if(s.charAt(i) == '(')
            dp[i] = 0;
        else{
            if(s.charAt(i - 1) == '(')
                dp[i] = dp[i - 2] + 2;
            else{
                if(i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '('){
                    dp[i] = dp[i - 1] + 2;
                    dp[i] += i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0;
                }
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)