32. Longest Valid Parentheses


Description

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

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Example

Another example is ")()())", 
where the longest valid parentheses substring is "()()", 
which has length = 4.

Translation

给定一个只包含字符’(’和’)’的字符串,找出最长有效(格式良好)的括号中的字符串的长度。

对于“(()”,最长的有效括号是“()”,长度= 2。

Ideas

采用栈,判断栈顶元素与当前元素是否匹配,匹配成功则弹出,不成功则压入栈,入栈的是索引值,不是字符。

遇到 ‘(‘ 入栈索引值

遇到 ‘)’ 先出栈,

如果栈为空,直接入栈

如果栈不空,用当前索引减去栈顶索引,即得新的有效格式的长度。

Accept Code

public static int longestValidParentheses(String s) {
    int ans = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.empty()) {
                stack.push(i);
            } else {
                ans = i - stack.peek() > ans ? i - stack.peek() : ans;
            }
        }
    }
    return ans;
}

转载请注明出处
本文链接:https://zdran.com/20180401.html