32. Longest Valid Parentheses.md

32. Longest Valid Parentheses

https://leetcode.com/problems/longest-valid-parentheses/

题目

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

Example 1:

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

Example 2:

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

思路

• 设置 stack, max, leftmost，分别表示栈，当前最长合法长度，合法左边界（初始值 -1）。

• 用 stack 存放左括号的下标，遇到右括号，先判断栈是否为空，若为空则更新 leftmost 为当前 index，原因是栈为空的话，则说明当前已经没有左括号可以与新来的右括号匹配，因为栈中存放的全是左括号的元素下标，所以我们可以认为：如果要继续往后匹配，必须把旧的合法左边界 leftmost 更新为当前 index，以便与后面括号的匹配。

• 每次遇到右括号都要计算 longest，栈不为空的话，长度为 index - 栈顶值 ，栈为空则为 index - leftmost，即当前与左边界的距离。

代码

• Java

class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() < 2)
            return 0;
        int n = s.length();
        int max = 0;
        int leftmost = -1;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            }
            else {
                if (stack.isEmpty()) {
                    // until here, not a valid parenthesis
                    leftmost = i;
                }
                else {
                    int j = stack.pop();
                    if (stack.isEmpty())
                        max = Math.max(max, i - leftmost);
                    else
                        max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }
}

• Python3

class Solution:
    def longestValidParentheses(self, s: str) -> int:   
        if not s or len(s) < 2:
            return 0
        
        n, longest, leftmost = len(s), 0, -1
        stack = []
        
        for i, ch in enumerate(s):
            if ch == '(':
                stack.append(i)
            else:
                if stack == []:
                    leftmost = i
                else:
                    j = stack.pop(-1)
                    if stack == []:
                        longest = max(longest, i - leftmost)
                    else:
                        longest = max(longest, i - stack[-1])
        return longest