题目描述
这是 LeetCode 上的32. 最长有效括号，难度为 Hard。
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()" 复制代码
示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()" 复制代码
示例 3：
输入：s = "" 输出：0 复制代码
提示：
- 0 <= s.length <= 3 * 10410^4104
s[i]为'('或')'
栈解法
从前往后扫描字符串 s。使用 i 来记录当前遍历到的位置，使用 j 来记录最近的最长有效括号的开始位置。
只对 '(' 进行入栈（入栈的是对应的下标），当遍历到 ) 的时候，由于栈中只有 '('，所以可以直接弹出一个 ( 与之匹配（如果有的话）。
再检查栈中是否还有 (，如果有使用栈顶元素的下标来计算长度，否则使用 j 下标来计算长度。
class Solution { public int longestValidParentheses(String s) { Deque<Integer> stack = new ArrayDeque<>(); int ans = 0; for (int i = 0, j = -1; i < s.length(); i++) { if (s.charAt(i) == '(') { stack.addLast(i); } else { if (!stack.isEmpty()) { stack.pollLast(); int top = j; if (!stack.isEmpty()) top = stack.peekLast(); ans = Math.max(ans, i - top); } else { j = i; } } } return ans; } } 复制代码
- 时间复杂度：每个字符最多进栈和出栈一次。复杂度为 O(n)O(n)O(n)
- 空间复杂度：O(n)O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.32 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
