【刷穿 LeetCode】32. 最长有效括号（困难）

宫水三叶的刷题日记

发布于 2021-02-20 09:39:19

3880

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

0 <= s.length <= 3 * 104
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)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.32 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 32/1916 。

为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-01-26，如有侵权请联系 cloudcommunity@tencent.com 删除

腾讯云开发者社区