题目
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 "()()"
思路与解法
看到这道题目首先想到的就是经典的括号匹配问题（利用栈），这道题与之有所不同，整个字符串并不一定满足括号匹配，我们所要找的是最长的括号匹配的子串。
第一种方法就是进行N次括号匹配：输入字符串的长度为N，则以
0~N-1
位置的字符为起点向后进行一次括号匹配，获得匹配的长度；最终返回所有长度中的最大值即可。时间复杂度为O( N 2 N^2 N2)。（这种方法我并没有使用，并不知道能否通过测试。）
下面介绍一种效率更高的算法：
定义数据
dp[i]
表示位于栈中第i个位置(从下到上)的连续出栈的字符串长度。（使用
dp
表示，是因为最初打算使用动态规划的思想来做，但最终实现与动态规划关系并不大）
同样利用栈的思想，从左到右遍历整个字符串S：1、如果
S[i]=='('
，则将
(
压入栈中；2、否则的话：①如果当前栈顶元素为
(
，即
stack[stackLen-1]=='('
，然后存在了一对匹配的括号，更新
dp
数组：
dp[stackLen-1] = dp[stackLen-1] + dp[stackLen] + 2
，
dp[i]
由三部分组成，之前在该位置弹出的字符串数量
dp[i]
、在下一个位置上弹出的字符串数量
dp[i+1]
、以及新增的一堆括号；然后将
dp[i+1]
置为0。②否则的话，将当前元素压入到栈中。
下面以一个具体实例来介绍一下该算法：
(()))(((()))())
上述图示也间接说明了
dp[i+1]
对
dp[i]
所起的作用
代码实现
此算法我才用go语言实现
func longestValidParentheses(s string) int {
stack := make([]byte, 0)
dp := make([]int, len(s)+1)
max := 0
if s=="" {
return 0
}
stack = append(stack, s[0])
for i:=1; i<len(s); i++ {
if s[i] == '(' {
stack = append(stack, s[i])
} else {
stackLen := len(stack)
if stackLen > 0 && stack[stackLen-1] == '(' {
stack = stack[:stackLen-1]
dp[stackLen-1] = dp[stackLen-1] + dp[stackLen] + 2
dp[stackLen] = 0
} else {
stack = append(stack, s[i])
}
}
}
for i:=0; i<len(s)+1; i++ {
if max < dp[i] {
max = dp[i]
}
}
return max
}
测试结果
此算法的时间复杂度为 O ( N ) O(N) O(N)，效率较高：
