【刷题记录】32. 最长有效括号-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
复制代码

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
复制代码

示例 3：

输入：s = ""
输出：0
复制代码

提示：

0 <= s.length <= 3 * 104
s[i] 为 ‘(‘ 或 ‘)’

二丶思路分析

栈

在之前的【刷题记录】20. 有效的括号中我们使用栈来实现了有效括号的检验
这道题在这个基础上

遍历字符串 s。使用 i 来记录当前遍历到的位置，使用 j 来记录最近的最长有效括号的开始位置。
对于遇到的每个 ( ，我们将它的下标放入栈中，
对于遇到的每个 ) ，我们先弹出栈顶元素表示匹配了当前右括号：
如果栈为空，说明当前的右括号为没有被匹配的右括号，使用 j 下标来计算长度。
如果栈不为空，使用栈顶元素的下标来计算长度。

三、代码实现

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 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();
                    res = Math.max(res, i - top);
                } else {
                    j = i;
                }
            }
        }
        return res;
    }
}
复制代码