[leetcode] Longest Valid Parentheses

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

---

Solution:

刚开始用的是$O(n^2)$O(n2)的下面这个代码：

class Solution {
public:
    int longestValidParentheses(string s) {
        int count;
        int sln = s.size();
        int maxx = 0, maxright = 0;
        for (int i=0, j; i<sln; ++i) {
            count = 0;
            for (j=i; j<sln; ++j) {
                if (s[j] == '(') {
                    count++;
                } else if(count > 0){
                    count--;
                    if(count == 0) {
                        maxright = j;
                    }
                } else {
                    break;
                }
            }
            if (maxx < maxright-i) {
                maxx = maxright-i+1;
                i = maxright;
            }
        }

        return maxx;
    }
};

后面发现其实可以在$O(n)$O(n)的时间内实现

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> index_stack;
        int sln = s.size(), maxx = 0, maxleft = 0;
        for (int i=0, j; i<sln; ++i) {
            if (s[i] == '(') {
                index_stack.push(i);
            } else if(index_stack.empty()) {
                maxleft = i;
            } else {
                index_stack.pop();
                if (index_stack.empty() && maxx < i - maxleft) {
                    maxx = i - maxleft;
                } else if (maxx < i - index_stack.top()) {
                    maxx = i - index_stack.top();
                }
            }
        }
        return maxx;
    }
};