每日一题：最长有效括号

题意

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

Solution

栈里面存左括号的位置，当遇到右括号时：

栈为空：记录这个位置，说明下一轮的合法括号可能从这里开始。

栈不为空：先弹出左括号表示匹配。

• 此时栈为空，说明之前可能还有合法括号，用当前下标减去之前记录的那个位置。
• 此时栈不为空，减去当前栈顶的位置即可（最接近的没有被匹配的左括号）。

Code

class Solution {
    public int longestValidParentheses(String s) {
        int res = 0, last = -1;
        Stack<Integer> st = new Stack<Integer>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(')
                st.push(i);
            else {
                if (st.size() > 0) {
                    st.pop();
                    if (st.size() > 0)
                        res = Math.max(res, i - st.peek());
                    else
                        res = Math.max(res, i - last);
                } else {
                    last = i;
                }
            }
        }
        return res;
    }
}