0032. Longest Valid Parentheses =============================== 题目信息 -------- :题号: 0032. 最长有效括号 :难度: Hard :主题: 字符串、栈、动态规划、双向扫描 :原题: `LeetCode 0032 `_ :重点: 从逐起点验证推导到维护失效边界,并复用以当前位置结束的最长有效段 题目重述 -------- 给定一个只包含 ``(`` 和 ``)`` 的字符串 ``s``,返回其中最长有效括号连续子串的长度。 一个连续子串有效,当且仅当其中每个左括号都由后面的右括号闭合,并且从子串左端开始扫描时,任意前缀中的 右括号数量都不超过左括号数量。答案必须来自原字符串中的连续区间,不能跳过字符重新拼接。 字符串长度位于 ``[0, 3 * 10^4]``。空字符串、全为左括号或全为右括号时,答案均为 ``0``。 自建示例 -------- * 多段连接:``s = "()(())"``,返回 ``6``;末尾的 ``(())`` 与前面的 ``()`` 连成完整区间; * 多余右括号:``s = ")(()())"``,返回 ``6``;下标 ``0`` 是任何有效区间都不能跨越的边界; * 多余左括号:``s = "(()(()"``,返回 ``2``;只有中间的 ``()`` 完整闭合; * 相邻有效段:``s = "()(()())"``,返回 ``8``;局部配对完成后还要连接左侧有效段; * 无法形成配对:``s = "((("``,返回 ``0``。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: int enumerateStarts(const std::string& s) { int best = 0; for (int start = 0; start < static_cast(s.size()); ++start) { int balance = 0; for (int end = start; end < static_cast(s.size()); ++end) { balance += s[end] == '(' ? 1 : -1; if (balance < 0) break; if (balance == 0) { best = std::max(best, end - start + 1); } } } return best; } int indexStack(const std::string& s) { std::vector boundaries{-1}; int best = 0; for (int index = 0; index < static_cast(s.size()); ++index) { if (s[index] == '(') { boundaries.push_back(index); continue; } boundaries.pop_back(); if (boundaries.empty()) { boundaries.push_back(index); } else { best = std::max(best, index - boundaries.back()); } } return best; } int dynamicProgramming(const std::string& s) { std::vector dp(s.size(), 0); int best = 0; for (int index = 1; index < static_cast(s.size()); ++index) { if (s[index] == '(') continue; if (s[index - 1] == '(') { dp[index] = 2; if (index >= 2) { dp[index] += dp[index - 2]; } } else { const int opening = index - dp[index - 1] - 1; if (opening >= 0 && s[opening] == '(') { dp[index] = dp[index - 1] + 2; if (opening >= 1) { dp[index] += dp[opening - 1]; } } } best = std::max(best, dp[index]); } return best; } int bidirectionalCounters(const std::string& s) { int best = 0; int left = 0; int right = 0; for (char current : s) { current == '(' ? ++left : ++right; if (left == right) { best = std::max(best, 2 * right); } else if (right > left) { left = 0; right = 0; } } left = 0; right = 0; for (int index = static_cast(s.size()) - 1; index >= 0; --index) { s[index] == '(' ? ++left : ++right; if (left == right) { best = std::max(best, 2 * left); } else if (left > right) { left = 0; right = 0; } } return best; } public: int longestValidParentheses(std::string s) { return dynamicProgramming(s); } }; 题解 ---- 逐起点余额 ~~~~~~~~~~ 固定起点 ``start`` 后,向右扫描并维护余额:左括号使余额加一,右括号使余额减一。余额为零时,左右括号数量 相等;此前余额从未为负,因此区间 ``[start,end]`` 有效。 余额首次变为负数时,当前前缀已经包含无法匹配的右括号。继续延长仍会保留这个非法前缀,所以同一起点不可能 再产生有效区间,可以立即停止。 ``enumerateStarts`` 按定义检查每个起点,正确性直接,但不同起点会反复读取相同后缀,最坏时间为 ``O(n²)``。继续优化需要保存已经发现的非法边界或有效区间,而不是重新计算余额。 失效边界与下标栈 ~~~~~~~~~~~~~~~~ 对一个以当前位置结束的有效后缀,真正决定其左边界的是最近一个不能跨越的位置: * 尚未匹配的左括号;跨过它会使区间内左括号过多; * 无法匹配的右括号;跨过它会使某个前缀右括号过多。 ``indexStack`` 用下标栈保存这些边界,初始放入 ``-1``,表示字符串开头之前的虚拟边界。遇到左括号时压入 下标;遇到右括号时先弹出一个位置,尝试匹配最近的未匹配左括号。 若弹出后栈为空,当前右括号无法匹配,它成为新的失效边界。若栈仍非空,当前右括号成功完成一层配对,栈顶 就是当前有效后缀左侧最近的不可跨越位置,因此长度为: .. code-block:: text index - boundaries.back() 栈顶之后不存在未匹配括号,跨过栈顶又必然破坏合法性,所以该长度恰好是以 ``index`` 结束的最长有效后缀。 每个下标最多入栈、出栈一次,时间降为 ``O(n)``。 结束位置状态 ~~~~~~~~~~~~ 下标栈保存全部未匹配边界。动态规划改为只保存每个结束位置的最优结果: .. code-block:: text dp[i] = 以 s[i] 结尾的最长有效括号子串长度 左括号不能结束有效括号串,因此 ``s[i] == '('`` 时 ``dp[i] = 0``。当 ``s[i] == ')'`` 时,只需处理两种 末尾结构。 直接配对 ~~~~~~~~ 若 ``s[i - 1] == '('``,末尾两个字符直接形成 ``()``。它们左侧若紧邻一个以 ``i - 2`` 结束的有效段,两个 区间可以连接: .. code-block:: text dp[i] = 2 + dp[i - 2] 下标越界时把前段长度视为零。例如 ``()()`` 的最后一对闭合后,需要连接前面的 ``()``,得到长度 ``4``。 包裹前段 ~~~~~~~~ 若 ``s[i - 1] == ')'``,前一位置可能已经结束一段长度为 ``dp[i - 1]`` 的有效区间。当前右括号若要继续向左 扩展,只能跳过这段完整区间,再检查其前一个字符: .. code-block:: text opening = i - dp[i - 1] - 1 若 ``opening`` 越界或 ``s[opening]`` 不是左括号,当前右括号不能形成更长有效后缀。若该位置是左括号,它与 当前右括号包住前一段有效区间,先得到: .. code-block:: text dp[i - 1] + 2 新形成的区间左侧还可能紧邻另一段有效括号,因此继续连接 ``dp[opening - 1]``: .. code-block:: text dp[i] = dp[i - 1] + 2 + dp[opening - 1] 这里没有跨过非法字符。``dp[i - 1]`` 只覆盖紧贴 ``i - 1`` 的有效段,``opening`` 是跳过该段后的相邻字符; ``dp[opening - 1]`` 也只吸收紧贴 ``opening`` 左侧的有效段。整个转移始终由连续相邻区间组成。 状态演化 ~~~~~~~~ 以 ``s = "()(())"`` 为例: .. list-table:: :header-rows: 1 * - ``i`` - 字符 - ``dp[i]`` - 状态来源 * - 0 - ``(`` - 0 - 左括号不能结束有效串 * - 1 - ``)`` - 2 - 下标 0 与 1 直接配对 * - 2 - ``(`` - 0 - 左括号不能结束有效串 * - 3 - ``(`` - 0 - 左括号不能结束有效串 * - 4 - ``)`` - 2 - 下标 3 与 4 直接配对 * - 5 - ``)`` - 6 - 跳过 ``dp[4]=2``,与下标 2 配对,再连接 ``dp[1]=2`` 最后一步若只计算 ``dp[4] + 2``,只能得到 ``(())`` 的长度 ``4``。连接 ``dp[1]`` 后,才得到完整连续区间 ``()(())`` 的长度 ``6``。 双向计数 ~~~~~~~~ 若只需要最长长度,不需要恢复区间边界,还可以只维护左右括号数量。 从左向右扫描时,``right > left`` 表示出现无法匹配的右括号,当前段不能再延伸,计数清零; ``left == right`` 表示当前重置点之后形成有效区间,用 ``2 * right`` 更新答案。 单次正向扫描无法处理末尾多余左括号,例如 ``(()``。因此再从右向左对称扫描:此时 ``left > right`` 表示 无法匹配的左括号,需要清零;两者相等时用 ``2 * left`` 更新答案。两个方向共同覆盖多余右括号和多余左括号 形成的边界,额外空间降为 ``O(1)``。 方法演进 ~~~~~~~~ ``enumerateStarts`` 为每个起点重新计算余额。``indexStack`` 把重复扫描压缩为未匹配边界,使每个字符只处理一次。 ``dynamicProgramming`` 将问题改写为“以每个位置结束的最长有效段”,通过前一有效段、配对左括号和左侧相邻段 复用已经完成的区间。公开入口采用该方法,因为状态与转移都直接对应连续区间。 ``bidirectionalCounters`` 进一步放弃具体边界,只保存两类括号数量,以两个扫描方向换取常数空间。 复杂度分析 ~~~~~~~~~~ 设字符串长度为 ``n``。 .. list-table:: :header-rows: 1 * - 方法 - 时间复杂度 - 工作空间 * - 逐起点余额 - ``O(n²)`` - ``O(1)`` * - 下标栈 - ``O(n)`` - ``O(n)`` * - 动态规划 - ``O(n)`` - ``O(n)`` * - 双向计数 - ``O(n)`` - ``O(1)`` 动态规划只计算每个 ``dp[i]`` 一次;双向计数各扫描字符串一次。返回值只保存长度,不计入额外空间。