最长有效括号

题目分析题解栈 总结

题目

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

分析

挺难的一道题，我想到了动态规划，想到了栈，但是一个都没有做出来。。有太多的点需要注意了，栈还是比较好理解的。

题解

栈

初始化一个栈，遇到做括号就将下标入栈，遇到右括号就弹栈。 如果弹栈之后栈为空，就将当前下表入栈。 如果弹栈之后下表不为空，更新结果。 注意要在最开始入栈一个 -1，比如“ （） ”，没有入栈一个-1的话，结果就是0。

public static int longestValidParentheses(String s) { int max = Integer.MIN_VALUE; Stack<Integer> stack = new Stack<Integer>(); 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 { max = Math.max(max, i - stack.peek()); // 弹栈后不为空，更新结果 } } } return max; }

总结

没啥好说的，难