LeetCode 32. 最长有效括号

LeetCode 

32. 最长有效括号

先正向获得所有的多余右括号位置，再反向获得所有的多余左括号位置，再插入-1(表示起始位置)和s.length()(表示结束位置)，然后将获得的矛盾位置数组排序，相邻位置之间的差值-1的最大值即为有效括号的最大长度。时间复杂度为O(nlogn).

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<char>st;
        vector<int>v;
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='(')
            {
                st.push(s[i]);
            }
            else
            {
                if(!st.empty())
                {
                    st.pop();
                }
                else
                {
                    v.push_back(i);
                }
            }
        }
        while(!st.empty())
        {
            st.pop();
        }
        for(int i=s.length()-1;i>=0;i--)
        {
            if(s[i]==')')
            {
                st.push(s[i]);
            }
            else
            {
                if(!st.empty())
                {
                    st.pop();
                }
                else
                {
                    v.push_back(i);
                }
            }
        }
        int ans=0;
        if(s.length()==0)return ans;
        v.push_back(-1);
        v.push_back(int(s.length()));
        sort(v.begin(),v.end());
        for(int i=0;i<v.size()-1;i++)
        {
            ans=max(ans,v[i+1]-v[i]-1);
        }
        return ans;
    }
};