Leetcode(32) Longest Valid Parentheses

发表于 | 分类于

Description

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

1
2
3
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

1
2
3
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

解法

括号匹配一般采用栈来处理，需要定义个start变量来记录合法括号串的起始位置，我们遍历字符串，如果遇到左括号，则将当前下标压入栈，如果遇到右括号，如果当前栈为空，说明之前没有左括号与之匹配，则将下一个坐标位置记录到start，如果栈不为空，则成功匹配这个右括号，将栈顶元素取出，此时若栈为空，说明从start位置到该右括号的所有括号均已匹配，更新结果和i - start + 1中的较大值，否则说明从当前出栈的前一个左括号的下一个开始均完成匹配（之所以不直接用匹配的左括号位置作为被减数是为了”(()()”的情况），更新结果和i - 栈顶元素中的较大值。

具体代码如下：

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
26
27
28
29
30
31
class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (stack.empty()) {
                    start = i + 1;
                } else {
                    stack.pop();
                    if (stack.empty()) {
                        res = max(res, i - start + 1);
                    } else {
                        res = max(res, i - stack.peek());
                    }
                }
            }
        }
        return res;
    }

    int max(int a, int b) {
        if (a > b) {
            return a;
        }
        return b;
    }
}