32. Longest Valid Parentheses，最长合法括号组

-- TOC --

题目分析
快使用Stack
- Python
- C++
- C

题目分析

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

Example 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:
Input: s = ""
Output: 0

从example可以看出，完整的输入并不一定是一个合法的括号组合，我们要做的是取其中最长的合法的那一段，计算其长度即可。

Constraints:

0 <= s.length <= 3 * 104

s[i] is '(', or ')'.

快使用Stack

一看到括号，就想到stack。

Python

自己捣鼓了一个算法出来，还是用stack判断括号的合法性，把所有合法的括号的位置都标注出来，然后最后再来计算得到最长连续括号的长度。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = []
        shadow = [0] * len(s)
        for i,x  in enumerate(s):
            if x==')' and stack:
                shadow[i] = shadow[stack.pop()] = 1
            elif x == '(':
                stack.append(i)
        lvp = tmp = 0
        for i in shadow:
            if i == 1:
                tmp += 1
            else:
                lvp = max(lvp,tmp)
                tmp = 0
        return max(lvp,tmp)

下面是个更好更烧脑的算法，更快，内存使用更少！

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        maxlen = 0
        for i,x  in enumerate(s):
            if x==')' and stack:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    maxlen = max(i-stack[-1], maxlen)
            elif x == '(':
                stack.append(i)
        return maxlen

仔细分析，这个算法能够很巧妙的解决类似这样的输入：()()。

C++

C

本文链接：https://cs.pynote.net/ag/leetcode/202401061/

-- EOF --

-- MORE --