leetcode 32 -- Longest Valid Parentheses

Longest Valid Parentheses

题目：
Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

---

题意：
给定一个字符串，找出其中满足括号匹配的最长字串的长度。

---

思路：
1.类似暴力求解，对每个子串进行验证，记录其括号匹配的长度，括号匹配原则，任意时刻，左括号个数一定大于右括号个数，且起始不能为右括号。时间复杂度O(n^2)，超时。
2.新建一个数组（长度和s相同）作为辅助记录字符串s的括号匹配过程，用栈来帮我们测试是否满足括号匹配，有满足匹配则把对应下标置为1，不满足为0，最后遍历辅助数组，最长连续为1的长度就是我们所需要的结果，时间复杂度为O(n)，AC

---

代码：

思路1

int longestValidParentheses(char* s) {
    char *p = s;
    char *q;
    int ret = 0;
    int left;
    int right;
    while(*p != '\0'){
        //首字符不能为右括号
        if(*p == ')'){
            ++p;
            continue;
        }else if(*p == '('){
            left = 1;
            right = 0;
            q = p+1;
            while(*q != '\0'){
                //printf("s:%s\n", q);
                //sleep(1);
                if(*q == '('){
                    left++;
                }else if(*q == ')'){
                    right++;
                }
                //满足匹配更新，不满足跳出循环
                if(right == left){
                    if(right+left > ret){
                        ret = right+left;
                        //printf("ret:%d\n", ret);
                    }
                }else if(right > left){
                    p = q;
                    ++q;
                    break;
                }
                ++q;
            }
            ++p;
        }
    }
    return ret;
}

手动测试过正确，但是leetcode上面显示超时

---

思路2

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int>sk;
        vector<int>ivec(s.length());
        //初始化
        for(int &i : ivec){
            i = 0;
        }
        for(int i = 0; i < s.length(); ++i){
            //注意栈保存的是对应字符的下标
            if(s[i] == '('){
                sk.push(i);
            }else if(s[i] == ')' && !sk.empty()){
                //当为')'时，栈若不为空，则里面一定为'('，满足匹配，标记为1
                ivec[i] = 1;
                ivec[sk.top()] = 1;
                sk.pop();
            }
        }
        int ret= 0;
        int tmp = 0;
        //找最长连续为1的
        for(const int &i : ivec){
            if(i == 1){
                tmp++;
            }else{
                tmp = 0;
            }
            if(ret < tmp){
                ret = tmp;
            }            
        }
        return ret;
    }
};