32. Longest Valid Parentheses (H)

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 3 * 104

• s[i] is '(', or ')'.

Solution:

Version 1: Stack

1.遍历给字符串中的所有字符 1.1若当前字符sindex为左括号'('，将当前字符下标index入栈（下标稍后有其他用处），处理下一字符 1.2若当前字符sindex为右括号')'，判断当前栈是否为空 1.2.1若栈为空，则accumulatedLen = 0，当前有效长度为0，处理下一字符（当前字符右括号下标不入栈） 1.2.2若栈不为空，则出栈（由于仅左括号入栈，则出栈元素对应的字符一定为左括号，可与当前字符右括号配对），判断栈是否为空 1.2.2.1若栈为空，则maxlen = max(maxlen, index-start+1)，更新当前最大匹配序列长度 1.2.2.2若栈不为空，则maxlen = max(maxlen, i-栈顶元素值)，更新当前最大匹配序列长度

Version2: dp

题解： 一般对于最长XX问题容易想到利用DP求解，在这题中利用逆向DP，设状态dpi为从i到len - 1中，以i开头的最长合法子串长度：

• 初始化：dplen - 1 = 0
• 如果si = ')'，则跳过，因为不可能有由'('开头的串
• 如果si = '('，则需要找到右括号和它匹配，可以跳过以i + 1开头的合法子串，则需要看j = i + dpi + 1 + 1是否为右括号。如果没越界且为右括号，那么有dpi = dpi + 1 + 2，此外在这个基础上还要将j + 1开头的子串加进来（只要不越界）

Version 3: Stack + dp

如果你看过前文 手把手解决三道括号相关的算法题，就知道一般判断括号串是否合法的算法如下：

Stack<Integer> stk = new Stack<>();
for (int i = 0; i < s.length(); i++) {
    if (s.charAt(i) == '(') {
        // 遇到左括号，记录索引
        stk.push(i);
    } else {
        // 遇到右括号
        if (!stk.isEmpty()) {
            // 配对的左括号对应索引，[leftIndex, i] 是一个合法括号子串
            int leftIndex = stk.pop();
            // 这个合法括号子串的长度
            int len = 1 + i - leftIndex;
        } else {
            // 没有配对的左括号
        }
    }
}

但如果多个合法括号子串连在一起，会形成一个更长的合法括号子串，而上述算法无法适配这种情况。

所以需要一个 dp 数组，记录 leftIndex 相邻合法括号子串的长度，才能得出题目想要的正确结果。

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stk = new Stack<>();
        // dp[i] 的定义：记录以 s[i-1] 结尾的最长合法括号子串长度
        int[] dp = new int[s.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 遇到左括号，记录索引
                stk.push(i);
                // 左括号不可能是合法括号子串的结尾
                dp[i + 1] = 0;
            } else {
                // 遇到右括号
                if (!stk.isEmpty()) {
                    // 配对的左括号对应索引
                    int leftIndex = stk.pop();
                    // 以这个右括号结尾的最长子串长度
                    int len = 1 + i - leftIndex + dp[leftIndex];
                    dp[i + 1] = len;
                } else {
                    // 没有配对的左括号
                    dp[i + 1] = 0;
                }
            }
        }
        // 计算最长子串的长度
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}