题解 | #最长的括号子串#

import java.util.*;


public class Solution {
    /**
     *
     * @param s string字符串
     * @return int整型
     */
     /**
    思路:保证栈中 只有栈底为最后的一个右括号，其余的位置只能放左括号

    遍历字符串
        如果当前字符是左括号加入栈中
        如果当前字符是右括号 则判断栈的大小
        如果栈的大小<=1 ,表示栈底要么没有元素 要么存在一个右括号
        将栈底元素更新为最新的右括号。
        如果栈的大小>1 ,表示栈中除了栈底的最右括号以外 还有一些左括号 那么把那些左括号弹出来 与右括号配对然后更新res值
      */
    public int longestValidParentheses (String s) {
        // write code here
        Stack<Integer> stack = new Stack<Integer>();

        stack.add(-1); //为满足最后一个右括号下标 我们将-1加入栈中
        int n = s.length();
        int res = 0;
        for (int i = 0 ; i < n ; i++) {
            if (s.charAt(i) == '(') {
                stack.add(i);
            } else {
                if (stack.size() > 1) {
                    stack.pop();
                    res = Math.max(res, i - stack.peek());
                }else {
                    stack.clear();
                    stack.add(i);
                }
            }
        }

        return res;
    }
}