题解 | 最长的括号子串

1、解题思路

1. 栈方法：使用栈来跟踪括号的匹配情况。栈中存储的是下标，初始时压入 -1 作为边界。遍历字符串： 遇到 '(' 时，将其下标压入栈。遇到 ')' 时，弹出栈顶元素： 如果栈为空，将当前下标压入栈作为新的边界。否则，计算当前有效子串长度（当前下标 - 栈顶元素）并更新最大值。时间复杂度：O(n)，空间复杂度：O(n)。
2. 动态规划：定义 dp[i] 表示以第 i 个字符结尾的最长有效括号子串的长度。状态转移： 如果 s[i] == ')' ： 若 s[i-1] == '('，则 dp[i] = dp[i-2] + 2。若 s[i-1] == ')' 且 s[i - dp[i-1] - 1] == '('，则 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]。时间复杂度：O(n)，空间复杂度：O(n)。
3. 双指针法：从左到右和从右到左各扫描一次，统计左右括号的计数： 当左右括号计数相等时，更新最大长度。当右括号多于左括号时，重置计数。时间复杂度：O(n)，空间复杂度：O(1)。

2、代码实现

C++

#include <stack>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    int longestValidParentheses(string s) {
        // write code here
        stack<int> st;
        st.push(-1);
        int max_len = 0;

        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                st.push(i);
            } else {
                st.pop();
                if (st.empty()) {
                    st.push(i);
                } else {
                    max_len = max(max_len, i - st.top());
                }
            }
        }
        
        return max_len;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int max_len = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    max_len = Math.max(max_len, i - stack.peek());
                }
            }
        }
        return max_len;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return int整型
#
class Solution:
    def longestValidParentheses(self , s: str) -> int:
        # write code here
        stack = [-1]
        max_len = 0
        for i, char in enumerate(s):
            if char == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_len = max(max_len, i - stack[-1])
        return max_len

3、复杂度分析

• 时间复杂度 O(n)
• 空间复杂度 O(n)