力扣：32-最长有效括号

题目描述

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0
 

提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'

来源：力扣（LeetCode）
题目链接：力扣-32.最长有效括号

解题思路

看到这道题，立马想到的就是用栈去解决，不出意外果然能用栈写

一般这种匹配括号的题都可以用栈来解决

这道题的思路就是创建一个栈，这里注意栈里面存的是下标。核心还是右括号匹配左括号，匹配失败时则将右括号加入到栈顶，这个右括号的下标是有作用的。这个下标可以当下一个连续括号子串的左边界，往后继续匹配时，如果栈不空的话，那么当前下标减去栈顶元素就是这个连续括号子串的长度。栈空的话说明当前字符是没有匹配的右括号，将它的下标入栈。

需要注意的是如果题目给定的字符串的第一个字符是左括号的话，那么我们遇到没有匹配的右括号时，栈中是没有右括号的，所以我们开始向栈中放一个-1的元素代替右括号

代码实现

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int>st;//新建一个栈
        st.push(-1);//开始放入-1代替右括号
        int ans=0;//结果
        //遍历题目所给字符串
        for(int i=0;isize();i++)
        {
            //如果是左括号，入栈
            if(s[i]=='(')
            st.push(i);
            else
            {
                //如果是右括号，栈顶出栈
                st.pop();
                //如果栈空的话说明当前右括号没有匹配，入栈，充当左边界
                if(st.empty())
                st.push(i);
                //如果栈不空的话，当前元素下标减去栈顶元素就是一个连续子串的长度
                else
                {
                    ans=max(ans,i-st.top());
                }
                
            }
        }
        return ans;
    }
};