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

一、题目描述

来源：力扣（LeetCode）

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

示例 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;
    }
}

复杂度分析

• 时间复杂度：
  网络异常，图片无法展示

  |
  , n为字符串的长度
• 空间复杂度：
  网络异常，图片无法展示

  |
  ， n为字符串的长度

运行结果

总结

这道题也是对前面做过的题目的一个加强变形。主要还是使用栈来实现括号的有效匹配。

针对不同的问题，选用合适的数据结构来更快捷的解决我们的问题。

继续加油~~