32. 最长有效括号

括号问题常常可以用栈来处理

• stack idx ; // 如果是左括号，则左括号的索引入栈
• vector v; // 记录全部有效括号的索引
  • 如果当前为右括号，且栈顶有左括号，则记录栈顶左括号的索引和当前右括号的索引。
  • 然后idx的栈顶出栈，把与当前右括号匹配的左括号的索引删除掉
• v中记录的是全部有效括号的索引，因此找到这里边最长的连续递增子串的长度即可
  • 由于弹出的顺序不同，v中的记录可能是乱序的。因此要先排序，再找连续递增子串

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> idx;  // 如果是左括号，则左括号的索引入栈
        vector<int> v;  // 如果当前为右括号，且栈顶为左括号，则记录栈顶左括号的索引和当前右括号的索引
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') { // 记录左括号的索引
                idx.push(i);
            } else if (s[i] == ')') { // 更新与当前右括号匹配的左括号的信息
                if (!idx.empty()) { //  防止栈顶为空
                    v.push_back(idx.top()); // 与右括号匹配的左括号的索引入转
                    v.push_back(i); // 有括号的索引入栈
                    idx.pop(); // 匹配过的左括号的索引出栈
                }
            }
        }

        sort(v.begin(), v.end());
        int ans = 0;
        int count = 1;
        for (int i = 1; i < v.size(); ++i) {
            if (v[i - 1] + 1 == v[i]) {
                count++;
                ans = max(ans, count);
            } else {
                count = 1;
            }
        }
        return ans;
    }
};

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        idx = []
        v = []
        for i in range(len(s)):
            if s[i] == '(':
                idx.append(i)
            elif (idx):
                v.append(idx.pop())
                v.append(i)
        v = sorted(v)
        ans = 0
        count = 1
        for i in range(len(v)):
            if v[i - 1] + 1 == v[i]:
                count += 1
                ans = max(ans, count)
            else:
                count = 1
        return ans