7/4题解

1.最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：利用栈

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxans = 0;
        stack<int> stk;
        stk.push(-1);//先放入一个-1
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                stk.push(i);//如果是左括号，就将下标放进去
            } else {
                stk.pop();//否则，先弹出
                if (stk.empty()) {
                    stk.push(i);//如果为空，放入右括号下标
                } else {
                    maxans = max(maxans, i - stk.top());//否则，匹配左右括号，计算长度
                }
            }
        }
        return maxans;
    }
};