[LeetCode] 032. Longest Valid Parentheses (Hard) (C++)

指数：[LeetCode] Leetcode 指标解释 (C++/Java/Python/Sql) Github: https://github.com/illuz/leetcode

---

032. Longest Valid Parentheses (Hard)

链接：

题目：https://oj.leetcode.com/problems/longest-valid-parentheses/ 代码(github)：https://github.com/illuz/leetcode

题意：

问一个字符串里最长的合法括号串的长度。

分析：

(C++)用栈来做，假设匹配就出栈，然后长度就是 cur - stack_top_pos 也就是 - 匹配的前一个位置。 O(n) time, O(n) space。(C++)栈消耗空间太多了。事实上能够维护 () 匹配的长度。只是可能出现 ())) 和 ((() 的情况。所以要前后各扫一遍。

O(n) time, O(1) space。

用较复杂的 DP 来做，只是空间可没解法 2 那么优了。刚看到我非常久前的一个解法，用太多空间了Orz。如今来看还是 1、2 的做法好。

代码：

解法 1:（C++）

class Solution { public: int longestValidParentheses(string s) { stack<int> lefts; int max_len = 0, match_pos = -1; // position of first // matching '(' - 1 for (int i = 0; i < s.size(); ++i) { if (s[i] == '(') lefts.push(i); else { if (lefts.empty()) // no matching left match_pos = i; else { // match a left lefts.pop(); if (lefts.empty()) max_len = max(max_len, i - match_pos); else max_len = max(max_len, i - lefts.top()); } } } return max_len; } };

解法 2:（C++）

class Solution { public: int longestValidParentheses(string s) { int max_len = 0, depth = 0, start = -1; // solve ((() for (int i = 0; i < s.size(); ++i) { if (s[i] == '(') ++depth; else { --depth; if (depth == 0) max_len = max(max_len, i - start); else if (depth < 0) { start = i; depth = 0; } } } // solve ())) depth = 0; start = s.size(); for (int i = s.size(); i >= 0; --i) { if (s[i] == ')') ++depth; else { --depth; if (depth == 0) max_len = max(max_len, start - i); else if (depth < 0) { start = i; depth = 0; } } } return max_len; } };

版权声明：本文博客原创文章，博客，未经同意，不得转载。

转载于:https://www.cnblogs.com/bhlsheji/p/4732833.html

相关资源：数据结构—成绩单生成器