企业官网建设流程全解析

题目描述：

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

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如"(()())"。

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""输出：0

解题思路：

方法一：动态规划（O(n)）

核心思路：

状态定义：

dp[i]= 以s[i]结尾的最长有效括号子串的长度。

状态转移:

情况1：s[i] == '('

dp[i] = 0（以左括号结尾不可能形成有效括号）

情况2：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]

具体过程示例：

s = ")()())"

最长长度 = 4✅

代码实现：

class Solution { public: int longestValidParentheses(string s) { int n = s.size(); vector<int> dp(n, 0); int maxLen = 0; for (int i = 1; i < n; i++) { if (s[i] == ')') { // 情况1：前一个是 '(' if (s[i-1] == '(') { dp[i] = (i >= 2 ? dp[i-2] : 0) + 2; } // 情况2：前一个是 ')'，且前面有对应的 '(' else if (i - dp[i-1] - 1 >= 0 && s[i - dp[i-1] - 1] == '(') { dp[i] = dp[i-1] + 2 + (i - dp[i-1] - 2 >= 0 ? dp[i - dp[i-1] - 2] : 0); } maxLen = max(maxLen, dp[i]); } } return maxLen; } };

复杂度分析：

方法二：栈（O(n)）

核心思路：

用栈存储下标：

• 遇到'('：入栈

• 遇到')'：弹出栈顶

  • 如果栈为空：把当前下标入栈（作为新的"最后一个未匹配的右括号"）

  • 如果栈不为空：当前有效长度 =i - 栈顶下标

具体过程示例：

s = ")()())"

栈初始: [-1]（哨兵） i=0 ')': 弹出-1，栈空，入栈0 → 栈 [0] i=1 '(': 入栈1 → 栈 [0, 1] i=2 ')': 弹出1，栈 [0]，长度 = 2-0 = 2 i=3 '(': 入栈3 → 栈 [0, 3] i=4 ')': 弹出3，栈 [0]，长度 = 4-0 = 4 i=5 ')': 弹出0，栈空，入栈5 → 栈 [5] 最长 = 4 ✅

代码实现：

class Solution { public: int longestValidParentheses(string s) { stack<int> stk; stk.push(-1); // 哨兵 int maxLen = 0; for (int i = 0; i < s.size(); i++) { if (s[i] == '(') { stk.push(i); } else { stk.pop(); if (stk.empty()) { stk.push(i); // 新的哨兵 } else { maxLen = max(maxLen, i - stk.top()); } } } return maxLen; } };

方法三：双指针（O(n) 空间 O(1)）

核心思路：

从左往右扫描，统计左右括号数量：

• left == right：更新最大长度

• right > left：重置

但这样会漏掉"(()"这种情况，所以需要从右往左再扫一遍：

• left == right：更新最大长度

• left > right：重置

代码实现：

class Solution { public: int longestValidParentheses(string s) { int maxLen = 0; int left = 0, right = 0; // 从左往右 for (char c : s) { if (c == '(') left++; else right++; if (left == right) { maxLen = max(maxLen, 2 * right); } else if (right > left) { left = right = 0; } } // 从右往左 left = right = 0; for (int i = s.size() - 1; i >= 0; i--) { if (s[i] == '(') left++; else right++; if (left == right) { maxLen = max(maxLen, 2 * left); } else if (left > right) { left = right = 0; } } return maxLen; } };

三种方法对比：

栈方法最直观，双指针空间最优。

关键细节：

1. 动态规划的边界处理

• i-2可能越界，需要判断i >= 2

• i - dp[i-1] - 1可能越界，需要判断>= 0

2. 栈方法为什么用-1作哨兵？

处理s[0] == ')'的情况，保证栈不为空。

3. 双指针为什么需要两次扫描？

• 从左往右：处理right > left的情况（如")()"）

• 从右往左：处理left > right的情况（如"(()"）

总结：