【Leetcode 热题 100】32. 最长有效括号

问题背景

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

数据约束

• $0\le s.length\le 3\times 10^4$
• $s[i]$ 为 ‘(’ 或 ‘)’

解题过程

这题可以用栈来解决，还是挺简单的，困难的是用动态规划来实现。
新年的第二天，偷偷懒，这题就留到手边事情告一段落，专门训练动态规划的时候再写一次。

具体实现

class Solution {
    public int longestValidParentheses(String s) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        for (int left = 0, right = 0; right < s.length(); right++) {
            // 左括号通通入栈
            if (s.charAt(right) == '(') {
                stack.push(right);
            } else {
                if (!stack.isEmpty()) {
                    stack.pop();
                    // 栈为空，结算整个范围上的最大值
                    if (stack.isEmpty()) {
                        res = Math.max(res, right - left + 1);
                    // 栈不为空，则结算当前有边界到栈顶位置之间的长度，注意长度的修正
                    } else {
                        res = Math.max(res, right - stack.peek());
                    }
                } else {
                    // 遇到栈为空的情形，移动左边界进行下一轮的计算
                    left = right + 1;
                }
            }
        }
        return res;
    }
}