[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 '(' – 1for (int i = 0; i < s.size(); ++i) {if (s[i] == '(')lefts.push(i);else {if (lefts.empty()) // no matching leftmatch_pos = i;else {// match a leftlefts.pop();if (lefts.empty())max_len = max(max_len, i – match_pos);elsemax_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;}};

却还是，会愚蠢的选择相互敌视的方式。即使背脊相抵，