整体思路

这段代码同样旨在解决 “最长有效括号” 问题，但它采用的是一种 动态规划 (Dynamic Programming) 的方法。这种方法通过构建一个DP表（dp 数组），从左到右逐步计算以每个字符为结尾的最长有效括号子串的长度。

算法的核心在于定义状态 dp[i] 并找出其状态转移关系。

状态定义：
- dp[i] 被定义为：以字符串 s 中第 i-1 个字符（即 s.charAt(i-1)）为结尾的最长有效括号子串的长度。
- 索引偏移：为了方便处理边界，代码在原始字符串 s 前面加了一个空格 " "，使得 s 的索引从1开始。这样，dp 数组的索引 i 就直接对应了新字符串的索引 i。
状态转移方程：
- dp[i] 的值只有在 s.charAt(i) 是一个右括号 ')' 时才可能大于0，因为一个有效的括号子串必然以 ')' 结尾。如果 s.charAt(i) 是 '('，dp[i] 默认为0。
- 当 s.charAt(i) == ')' 时，我们需要寻找一个与之匹配的左括号 '('。这里有两种主要情况：
  a. 情况 1：形如 ...()
  - 如果 s.charAt(i-1) 是一个 '('，那么 s.charAt(i) 和 s.charAt(i-1) 构成了最简单的一对有效括号 ()。
  - 这个 () 的长度是 2。它还可以连接在 s.charAt(i-2) 结尾的有效子串后面。
  - 因此，状态转移方程为：dp[i] = dp[i-2] + 2。
    b. 情况 2：形如 ...))
  - 如果 s.charAt(i-1) 也是一个 ')'，那么 s.charAt(i) 需要去匹配更左边的某个 '('。
  - 我们知道，以 s.charAt(i-1) 结尾的有效子串长度是 dp[i-1]。那么，这个子串的起始位置就是 i - 1 - dp[i-1] + 1。它所需要匹配的左括号就在这个起始位置的前一个，即索引 i - 1 - dp[i-1] 的位置。
  - 我们检查 s.charAt(i - 1 - dp[i-1]) 是否为 '('。
  - 如果匹配成功：
    - 新形成的这个大括号 (...) 的长度是 dp[i-1] + 2。
    - 并且，这个大括号还可以连接在它前面的另一个有效子串后面。这个“前面的有效子串”是以 s.charAt(i - 2 - dp[i-1]) 结尾的，其长度为 dp[i - 2 - dp[i-1]]。
    - 因此，总长度为：dp[i] = dp[i-1] + 2 + dp[i - 2 - dp[i-1]]。
最终结果：
- 在填充 dp 数组的过程中，dp[i] 只是以 s.charAt(i) 为结尾的最长长度。全局的最长长度可能是任何一个 dp[i] 的值。
- 因此，需要一个 ans 变量来实时记录并更新所有 dp[i] 中的最大值。

完整代码

class Solution {/*** 找到字符串中最长的有效括号子串的长度。* @param s 只包含 '(' 和 ')' 的字符串* @return 最长有效括号子串的长度*/public int longestValidParentheses(String s) {// ans: 用于存储全局的最长有效括号子串长度。int ans = 0;// 技巧：在 s 前面加一个空格，使得索引从 1 开始，方便处理边界情况 dp[i-2]。s = " " + s;// dp 数组：dp[i] 表示以 s.charAt(i) 结尾的最长有效括号子串的长度。int[] dp = new int[s.length()];// 从索引 2 开始遍历，因为最短的有效括号 "()" 长度为 2。for (int i = 2; i < s.length(); i++) {// 只在遇到右括号时才可能形成有效子串if (s.charAt(i) == ')') {// 情况 1: 子串形如 ".....()"if (s.charAt(i - 1) == '(') {// 长度 = 前面有效子串的长度 (dp[i-2]) + "()" 的长度 (2)dp[i] = dp[i - 2] + 2;} // 情况 2: 子串形如 ".....))"// 且 s.charAt(i-1) 结尾的子串是有效的 (dp[i-1] > 0)// 我们需要检查 s[i-1-dp[i-1]] 是否是与之匹配的'('else if (i - 1 - dp[i - 1] > 0 && s.charAt(i - 1 - dp[i - 1]) == '(') {// 长度 = s[i-1]结尾的子串长度 + 新匹配的"()"长度 + 更前面连接的有效子串长度dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i-1]];}}// 每次计算完 dp[i]后，都用它来更新全局最大值 ans。ans = Math.max(ans, dp[i]);}return ans;}
}

时空复杂度

时间复杂度：O(N)

字符串拼接：s = " " + s; 在Java中会创建一个新的字符串，这需要 O(N) 的时间。
循环：算法的核心是一个 for 循环，它从 i = 2 遍历到 s.length() - 1。这个循环严格地执行 N-1 次（N 为原字符串长度）。
循环内部操作：
- 在循环的每一次迭代中，执行的都是常数次的操作：字符访问 charAt()、数组访问 dp[]、加减法和 Math.max。
- 这些操作的时间复杂度都是 O(1)。

综合分析：
算法的总时间复杂度是 O(N) (字符串拼接) + O(N) (循环) = O(N)。

空间复杂度：O(N)

主要存储开销：
- String s = " " + s;: 创建了一个新的字符串对象，其长度为 N+1，占用了 O(N) 的空间。
- int[] dp = new int[s.length()]: 创建了一个 dp 数组，其长度也为 N+1，占用了 O(N) 的空间。

综合分析：
算法所需的额外空间主要由新的字符串对象和 dp 数组决定。因此，其空间复杂度为 O(N)。