• 刷题仓库地址
• 4. Median of Two Sorted Arrays
• 10. Regular Expression Matching
• 23. Merge k Sorted Lists
• 25. Reverse Nodes in k-Group
• 30. Substring with Concatenation of All Words
• 32. Longest Valid Parentheses
• 37. Sudoku Solver

---

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