Leetcode-32-最长有效括号

发表于 | 分类于

题目

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”
示例 2:

输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”

栈

对于括号匹配问题, 最经典的处理方法是使用栈.

遍历字符串:

  • 遇到(时, 将其下标入栈
  • 遇到)时, 说明括号匹配正常. 出栈并计算当前下标能够成的有效括号子串.

问题就在于如何计算出栈时的最长有效括号字串.

我们可以先将-1置于栈底.

  • 如果出栈之后栈底不为空, 则将当前的下标减去栈顶, 就是当前的有效括号子串.
  • 如果出栈之后栈底为空, 那么将当前下标(必为右括号)的下标) 放入栈底即可.

过程如图所示

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestValidParentheses(String s) {
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(-1); 
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }
}