32.最长有效括号
32. 最长有效括号
鲁迅说过，项目告一个段落后，我们就可以重启二哥的 LeetCode 刷题笔记了，
希望大家能够坚持下去，一起进步。
题意
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
难度
困难
示例
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
分析
还记得有效括号那道题吗？
020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7-
20240201152218.png
当时，我们利用了栈这个数据结构，当遇到一个右括号，就看一看栈内有没有与之匹配的
左括号，如果栈为空或者说栈顶的左括号与之不匹配（除了小括号()还有中括号[]和大括
号{}），那么它就不是一个有效的括号序列。
那这道题我们同样可以使用栈这个数据结构来解决。先来回顾一下栈的基本操作：
stack.push(-1); // 入栈
stack.pop(); // 出栈
stack.peek(); // 查看栈顶元素
接下来，我们需要搞清楚最长有效括号子串的特点：
• 每一个左括号 ‘(’ 都有一个对应的右括号 ‘)’。
• 括号之间的嵌套关系是正确的，比如说 (()())、((()))、()()()。
然后，我们需要解决如何得出最长有效括号子串的长度。
新建一个栈，用来存放括号的下标。由于下标是从 0 开始的，我们可以在栈中放入一个
-1，表示栈底，这样更方便计算边界条件。
比如说对于 ()，初始状态是 [-1]，遇到左括号 (，我们将它的下标压入栈中，此时栈内是
[-1,0]。
遇到右括号 )，我们将栈顶的元素弹出，此时栈内是 [-1]，说明是一个有效的括号子串，
长度为右括号的下标减去栈顶元素的下标 1 - (-1)，即为 2。
032.%E6%9C%80%E9%95%BF%E6%9C%89%E6%95%88%E6%8B%AC%E5%8F%B7-
20240530144039.png
比如说对于 )()，初始状态是 [-1]，遇到右括号 )，我们将栈顶的元素弹出，此时栈内是
[]，说明没有匹配的左括号，我们将当前右括号的下标压入栈中，此时栈内是 [0]。
遇到左括号 (，我们将它的下标压入栈中，此时栈内是 [0,1]。
遇到右括号 )，我们将栈顶的元素弹出，此时栈内是 [0]，说明是一个有效的括号子串，
长度为右括号的下标减去栈顶元素的下标 2 - 0，即为 2。
032.%E6%9C%80%E9%95%BF%E6%9C%89%E6%95%88%E6%8B%AC%E5%8F%B7-
20240530144700.png
遍历字符串，遇到左括号 (，将它的下标压入栈中；当遇到右括号时，将栈顶的元素弹
出，此时有两种情况：
• 如果栈为空，说明当前的右括号没有与之匹配的左括号，我们将当前的右括号的下标
压入栈中
• 如果栈不为空，说明当前的右括号与栈顶的左括号匹配，我们计算当前的右括号与栈
顶的左括号的下标之差，即为当前的有效括号子串的长度
具体代码实现：
class Solution {
public int longestValidParentheses(String s) {
int ans = 0; // 用于记录最长有效括号长度
Stack<Integer> sta = new Stack<>(); // 栈用于存放索引
sta.push(-1); // 初始化栈，放入一个初始值 -1
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
sta.push(i); // 遇到左括号，将其索引压入栈
} else {
sta.pop(); // 遇到右括号，弹出栈顶元素
if (sta.isEmpty()) {
sta.push(i); // 如果栈为空，说明没有匹配的左括号，将当前索引压入栈
} else {
ans = Math.max(ans, i - sta.peek()); // 计算有效括号长度，并更新最大值
}
}
}
return ans; // 返回最长有效括号长度
}
}
假设字符串为 s = "(()))())("，我们来模拟一下整个题解过程：
①、初始化栈 sta = [-1]
②、遍历字符串：
1. i = 0, s.charAt(i) = '('，将索引 0 压入栈，sta = [-1, 0]
2. i = 1, s.charAt(i) = '('，将索引 1 压入栈，sta = [-1, 0, 1]
3. i = 2, s.charAt(i) = ')'，弹出栈顶元素 1，栈不为空，计算长度 2 - 0 = 2，更新 ans
=2
4. i = 3, s.charAt(i) = ')'，弹出栈顶元素 0，栈不为空，计算长度 3 - (-1) = 4，更新
ans = 4
5. i = 4, s.charAt(i) = ')'，弹出栈顶元素 -1，栈为空，将索引 4 压入栈，sta = [4]
6. i = 5, s.charAt(i) = '('，将索引 5 压入栈，sta = [4, 5]
7. i = 6, s.charAt(i) = ')'，弹出栈顶元素 5，栈不为空，计算长度 6 - 4 = 2，ans = 4
（不变）
8. i = 7, s.charAt(i) = ')'，弹出栈顶元素 4，栈为空，将索引 7 压入栈，sta = [7]
9. i = 8, s.charAt(i) = '('，将索引 8 压入栈，sta = [7, 8]
最终，最长有效括号长度为 4。
032.%E6%9C%80%E9%95%BF%E6%9C%89%E6%95%88%E6%8B%AC%E5%8F%B7-
20240530145324.png
虽然没有 beat 100%，但题解非常容易懂，也很容易记住，考虑到这是一道 hard 题，这
样的结果已经很不错了。
笔试的时候，也要优先解出题目，然后再考虑优化，不要一开始就想着写出最优解，这样
反而会让自己陷入困境。
总结
这道题依然考察的是栈这个数据结构，只不过是在有效括号的基础上，增加了一个长度的
计算，所以我们只需要在遍历的过程中，不断更新最长有效括号的长度即可。
推荐阅读：
• 二哥的 Java 进阶之路：栈
• 二哥的 Java 进阶之路：双端队列
当然了，Java 已经不再推荐使用 Stack 这个类，而是使用 Deque 接口的实现类
ArrayDeque，因为 Stack 继承了 Vector，而 Vector 是线程安全的，所以 Stack 的所有方法
都是同步的，性能较差。
class Solution {
public int longestValidParentheses(String s) {
int ans = 0; // 用于记录最长有效括号长度
Deque<Integer> sta = new ArrayDeque<>(); // 栈用于存放索引
sta.push(-1); // 初始化栈，放入一个初始值 -1
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
sta.push(i); // 遇到左括号，将其索引压入栈
} else {
sta.pop(); // 遇到右括号，弹出栈顶元素
if (sta.isEmpty()) {
sta.push(i); // 如果栈为空，说明没有匹配的左括号，将当前索引压入栈
} else {
ans = Math.max(ans, i - sta.peek()); // 计算有效括号长度，并更新最大值
}
}
}
return ans; // 返回最长有效括号长度
}
}
仅仅是将 Stack 替换为 ArrayDeque，其他逻辑没有任何改变，但题解效率已经得到了不
小幅度的提升。
032.%E6%9C%80%E9%95%BF%E6%9C%89%E6%95%88%E6%8B%AC%E5%8F%B7-
20240530150131.png
力扣链接：https://leetcode.cn/problems/longest-valid-parentheses/