最长有效括号

发表于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

LeetCode每日一题，32.Longest Valid Parentheses

先看题目描述

大意就是给定只包括 ( 和 ) 的字符串，返回最长的包括有效括号子串的长度

算法和思路

看到涉及括号匹配，第一反应就是用栈，但始终没想出来，后来看了题解才明白

具体做法是我们始终保持栈底元素为当前已经遍历过的元素中 最后一个没有被匹配的右括号的下标，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：

  • 对于遇到的每个 { ，我们将它的下标放入栈中
  • 对于遇到的每个 }，我们先弹出栈顶元素(个人理解：若弹出的栈顶元素代表左括号，栈是不可能为空的，弹出栈顶元素以后栈为空，说明这个右括号前面没有可以和它匹配的左括号)表示匹配了当前右括号：
    • 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的 最后一个没有被匹配的右括号的下标
    • 如果栈不为空，当前右括号的下标减去栈顶元素即为 以该右括号为结尾的最长有效括号的长度

我们从前往后遍历字符串并维护最长有效括号的长度即可

需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的最后一个没有被匹配的右括号的下标，为了保持统一，我们在一开始的时候往栈底放入一个值为 -1 的元素

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        int[] dp = new int[len];
        int res = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            }
            else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }
}