[leetcode] 32. 最长有效括号

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 10⁴
• s[i] 为 ‘(’ 或 ‘)’

解题方法

方法一：栈

利用栈先进后出的特性，每次匹配到'('字符，将'('字符的下标位置入栈；当匹配到')' 字符时，将栈顶一个'('字符的下标位置出栈，出栈的'('字符就是对应')'字符匹配的左括号。设匹配到')' 字符下标位置为j，对应出栈'('字符下标位置为i，j - i + 1即为当前的’)'字符匹配的括号长度。

通过上面这种方式我们能求出所有’)'对应'('的括号长度，取其中的最大值就是最长有效括号子串的长度吗？答案是否定的。还有一种情况，虽然匹配到了当前')'匹配到了'('，但是与匹配的'('相邻的前面字符串中也可能存在有效的括号子串。此时，就需要将前面子串的括号长度相加。

举个例子，设字符串为"$()()$"，此时绿色的括号匹配长度是2，但我们还需要加上前面红色括号的匹配长度，才能求出最长有效括号子串的长度。

友情提示：以下是正确思路

那我们需要怎么做呢？其实也很简单，只需要提供一个变量start，用来记录有效括号子串的起始位置。初始栈为空时，加入的第一个'('的下标即为有效括号子串的起始位置。而当栈中没有'('，而又匹配到')'时，原来的start位置废弃，后面加入的第一个'('的下标即为新的start。那么当匹配到')'时，如何计算最长有效括号子串的长度呢？分以下两种情况讨论。

• 第一种，当匹配到的字符')'有对应出栈'('字符，且'('出栈后栈不为空。设当前')'下标为j，'('出栈后栈顶元素为i，则当前')'匹配的有效括号子串的长度为j - i。
• 第二种，当匹配到的字符')'有对应出栈'('字符，且'('出栈后栈为空。设当前')'下标为j，则当前')'匹配的有效括号子串的长度为j - start + 1。

取上面两种情况的最大值即为最长有效括号子串的长度。

java代码

public int longestValidParentheses(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    // 记录有效子串的起始位置
    int start = 0;
    int max = 0;
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            stack.push(i);
        } else if (c == ')') {
            if (stack.isEmpty()) {
                start = i + 1;
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    // 栈为空时，有效子串的长度 = 右括号的位置 - 有效子串的起始位置 + 1
                    max = Math.max(max, i - start + 1);
                } else {
                    // 栈不为空时，有效子串的长度 = 右括号的位置 - 栈顶元素的位置，因为栈顶元素的下一个位置是匹配的'('
                    max = Math.max(max, i - stack.peek());
                }
            }
        }

    }
    return max;
}

复杂度分析

时间复杂度：$O(N)$，$N$为字符串长度。需要遍历一次字符串。
空间复杂度：$O(N)$，需要提供栈的存储空间。

方法二：贪心

方法一需要用栈存储左括号位置，那么有没有一种方法只使用$O(1)$的常数空间呢？答案是有的，不过需要遍历两次字符串，我说一下思路。

第一次遍历，我们需要从头到尾遍历字符串，我们记$left$为匹配的'('数量，$right$为匹配的')'数量数量。当$right>left$时，$left$和$right$置为$0$；当$right==left$时，计算当前字符串的有效长度为$2\times right$，并且记录目前为止最长字符串长度。此次遍历，有一种情况没有考虑到。例如字符串"$(()$"，当$left$一直大于$right$时，是求不出最长长度的。

所以需要第二次遍历，这次我们从尾到头遍历字符串。还是记$left$为匹配的'('数量，$right$为匹配的')'数量数量。当$left>right$时，$left$和$right$置为$0$；当$left==right$时，计算当前字符串的有效长度为$2\times left$，并且记录目前为止最长字符串长度。

java代码

public int longestValidParentheses(String s) {
    int left = 0, right = 0;
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            left += 1;
        } else {
            right += 1;
        }
        if (right > left) {
            left = 0;
            right = 0;
        } else if (right == left) {
            max = Math.max(right * 2, max);
        }
    }
    left = right = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        char c = s.charAt(i);
        if (c == '(') {
            left += 1;
        } else {
            right += 1;
        }
        if (left > right) {
            left = 0;
            right = 0;
        } else if (left == right) {
            max = Math.max(left * 2, max);
        }
    }
    return max;
}

复杂度分析

时间复杂度：$O(N)$，$N$为字符串长度。需要遍历两次字符串。
空间复杂度：$O(1)$，只需要存储常数级别的变量。

相似题目

[leetcode] 20. 有效的括号

• 个人公众号
  
• 个人小游戏