最长的括号子串长度

维护一个栈，保存左括号的下标，如果遇到右括号，则弹出一个左括号，并且更新长度。注意到一个特殊情况如(())()，我们需要保存栈空时的起始节点：

//
// Created by jt on 2020/8/31.
//
#include <stack>
#include <iostream>
using namespace std;

class Solution {
public:
    /**
     *
     * @param s string字符串
     * @return int整型
     */
    int longestValidParentheses(string s) {
        // write code here
        stack<int> st;
        int maxVal = 0, last = -1;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') st.push(i);
            else {
                if (st.empty()) last = i;
                else {
                    st.pop();
                    maxVal = st.empty() ? max(maxVal, i-last) : max(maxVal, i-st.top());
                }
            }
        }
        return maxVal;
    }
};