LeetCode 32. 最长有效括号

LeetCode 32. 最长有效括号

原题地址：点击跳转

题目描述

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的有效括号子串。

示例

()()有效长度为4,((()))有效长度为2。

解题思路

这道题唯一的坑点就是题目询问的是最长有效长度，不是括号有几对。
开一个stack，如果遇到字符 (，将它的下标压入栈中。因为左括号有可能会被后续的右括号匹配。如果遇到字符 )，先从栈中弹出一个元素。弹出的过程相当于尝试匹配当前右括号与前面的左括号。

代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int ans = 0;
        stack<int> st;
        st.push(-1);
        for (int i = 0; i < s.size(); 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;
    }
};