【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;}
}