指数：

Github:

---

032. Longest Valid Parentheses (Hard)

链接：

题目：

代码(github)：

题意：

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

分析：

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

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

3. 用较复杂的 DP 来做，只是空间可没解法 2 那么优了。刚看到，用太多空间了Orz。如今来看还是 1、2 的做法好。

代码：

解法 1:（C++）

class Solution {public:    int longestValidParentheses(string s) {        stack
     
       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;    }};

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