2025年- H99-Lc207--32.最长有效括号(栈、动态规划)--Java版

1.题目描述

2.思路

把（压入栈中，并且把（放入栈顶。在遍历过程中遇到的每个），我们从栈顶弹出（，如果栈顶没有（，或者遍历完整个字符串栈中仍有元素，那么该字符串是无效的。
任何一个有效的括号字符串，其长度必然是偶数。比如 () 长度是2，(()) 长度是4，()() 长度也是4。一个长度为奇数的括号字符串（如 (、())）永远不可能是有效的。


长度为1的子串：比如 ( 或者 )。它们不可能是有效的，因为无法配对。

长度为2的子串：比如 ()。这是我们能找到的最短的、可能有效的括号组合。

现在，我们再来看代码的逻辑：

外层循环用 i 来确定子串的起点。
内层循环用 j 来确定子串的终点（不包含j）。

子串的长度是 j - i。
（（））
0123

例子

3.代码实现

方法1:超时

class Solution {public boolean isValid(String s){Stack<Character> st=new Stack<Character>();//判断括号是不是有效的括号组合for(int i=0;i<s.length();i++){ // 遇到左括号，入栈if(s.charAt(i)=='('){st.push('(');}else// 遇到右括号 ')'{//遇到 ）情况,此时栈不空并且栈顶元素是 (，弹出）去匹配if(!st.empty()&&st.peek()=='('){st.pop();}// 如果栈为空，或者栈顶不是 '(', 说明无法匹配，是无效字符串else{return false;}}}// 如果为空，所有括号都匹配了，返回true；否则说明有未匹配的左括号，返回false。return st.empty();}public int longestValidParentheses(String s) {int maxlen=0;//i确定子串的起点for(int i=0;i<s.length();i++){//j确定子串的终点，因为子串不可能是1个括号，奇数子串没有意义for(int j=i+2;j<=s.length();j=j+2){if(isValid(s.substring(i,j))){maxlen=Math.max(maxlen,j-i);}}}return maxlen;}
}

方法二：代研究

class Solution {public int longestValidParentheses(String s) {int maxlen = 0;Stack<Integer> stack = new Stack<>();// 关键：放入-1作为参照物stack.push(-1); for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(') {// 遇到 '(', 把索引压入栈stack.push(i);} else { // 遇到 ')'// 弹出一个元素stack.pop();if (stack.empty()) {// 如果栈空了, 说明当前的 ')' 没有匹配的 '('// 把当前 ')' 的索引放入，作为新的参照物stack.push(i);} else {// 如果栈不空, 计算当前有效长度// 长度 = 当前索引 - 新的栈顶索引maxlen = Math.max(maxlen, i - stack.peek());}}}return maxlen;}
}