问题描述
Given a string containing just the characters '(' and ')', find 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
Constraints:
- 0 <= s.length <= 3 * 10^4
- s[i] is '(', or ')'.
问题分析
首先，既然要判断括号是否闭合匹配，那么常规做法是利用stack，stack中只会压入左括号：
- 如果当前字符为左括号，则压栈
- 如果当前字符为右括号，则弹栈; 如果栈顶元素非左括号，说明已经没有可匹配的，直接返回false
- 字符传遍历完后，只需判断栈是否为空即可
有了以上基础以后，那么这道题最暴力的解法无非就是从字符串每个位置开始，判断不同长度下的子串是否符合条件，并更新最大长度，最后返回。
很明显，这个做法的时间复杂度为O(N^2)，我们需要进一步降低时间复杂度，否则肯定会TLE。所以我们采取以下措施来减少不必要的比较过程：
- 先计算出左括号和右括号的
prefix sums；这样针对每一个子串，我们可以在常量时间内计算出左括号数量和右括号数量是否相等；如果不等，直接跳过。同时，对于不相等的情形，我们将待检测子串的末尾位置向后移动M个位置，M等于左括号和右括号的差值绝对值。这么做的目的是，只有加上这个差异绝对值以后，左括号和右括号才有可能相等进入后续判断。同时，针对连续左括号或者右括号的情形，也能快速增加子串末尾下标位置，大幅减少无效的比较。 - 如果相等，且当前子串为闭合匹配的子串，那么下一次检测的起始点移动至当前子串末尾。这么做的目的是基于这样的考虑：如果一个字符串为闭合匹配的，那么它要么由多个连续闭合匹配的子串构成，要么只有其本身是闭合匹配的。移动至当前子串末尾可以减少不必要的检测。
初始解法代码如下:
初始解法
func longestValidParentheses(s string) int {
ans := 0
cur := 0
// prefix sum of '(' and ')'
psleft, psright := make(map[int]int), make(map[int]int)
ls, rs := 0, 0
for i := 0; i < len(s); i++ {
if s[i] == '(' {
ls++
} else {
rs++
}
psleft[i] = ls
psright[i] = rs
}
for i := 0; i < len(s)-1; i++ {
// 如果起始字符不为 '(', 直接跳过
if s[i] == ')' {
// cur 表示以i为起始的最大匹配子串长度
cur = 0
continue
}
hasValid := false
// 括号匹配至少长度为2，因此初始的增量为1 (左右闭区间)
gap := 1
for j := i + 1; j < len(s); j += gap {
leftnum, rightnum := 0, 0
// 计算当前待check的子串中 '(' 和 ')' 的数量是否一致
if i == 0 {
leftnum = psleft[j]
rightnum = psright[j]
} else {
leftnum = psleft[j] - psleft[i-1]
rightnum = psright[j] - psright[i-1]
}
// 如果不一致，直接跳过；同时将增量更新为差异值的绝对值
// 这么做的目的是至少再加上这么多字符后，左右括号的数量才有可能一致;
// 同时对于连续左括号或者右括号的情况，能够快速找到下一个数量匹配的位置，大幅降低整体的比较次数
if leftnum != rightnum {
gap = abs(leftnum - rightnum)
continue
}
if isValid(s, i, j) {
hasValid = true
cur += j - i + 1
if cur > ans {
ans = cur
}
// 如果这里找到了，则下一次check的字符串起始位置移动到已匹配的末尾，继续下一轮的匹配
i = j
break
}
}
// 如果本轮没有找到，则将cur重置，进入下一轮查找
if !hasValid {
cur = 0
}
}
return ans
}
func isValid(s string, start int, end int) bool {
if start == end || s[start] == ')' || s[end] != ')' || (end-start+1)%2 != 0 {
return false
}
stack := stack{}
stack.Push(s[start])
for i := start + 1; i <= end; i++ {
if s[i] == ')' {
top := stack.Pop()
if top == '0' {
return false
}
} else {
stack.Push(s[i])
}
}
return len(stack.list) == 0
}
type stack struct {
list []byte
}
func (s *stack) Push(item byte) {
s.list = append(s.list, item)
}
func (s *stack) Pop() byte {
if len(s.list) == 0 {
return '0'
}
ans := s.list[len(s.list)-1]
s.list = s.list[:len(s.list)-1]
return ans
}
func (s *stack) Top() byte {
if len(s.list) == 0 {
return '0'
}
return s.list[len(s.list)-1]
}
func abs(a int) int {
if a < 0 {
return -1 * a
}
return a
}
优化解法
初始解法已经可以AC，但是耗时略久，我的提交显示耗时48ms。逛了评论区，发现一个更巧妙的解法:
还是利用栈来判断是否闭合匹配，只不过做了一些调整，解法如下：
- 扫描字符串，如果当前字符为 '('，则压栈
- 如果当前字符串为 ')'，则判断栈顶元素:
- 如果栈顶元素为 '('，说明匹配；进行pop
- 如果栈顶元素为 ')', 说明不匹配，继续压栈
- 扫描完毕后，如果栈为空，说明整个字符串都是符合条件的; 如果不为空，说明剩下的是那些无法进行匹配的字符的位置 只要找出这些无法匹配位置之间的最大间隔，就是最大匹配子串长度
这个解法的巧妙之处在于不是直接查找符合条件的子串长度，而是从相反方向入手，将符合条件的子串都pop掉，通过判断遗留在栈中的元素之间的间隔来获取弹出的子串的最大长度。
// 1. 扫描字符串，如果当前字符为 '('，则压栈
// 2. 如果当前字符串为 ')'，则判断栈顶元素:
// 1. 如果栈顶元素为 '('，说明匹配；进行pop
// 2. 如果栈顶元素为 ')', 说明不匹配，继续压栈
// 3. 扫描完毕后，如果栈为空，说明整个字符串都是符合条件的; 如果不为空，说明剩下的是那些无法进行匹配的字符的位置
// 只要找出这些无法匹配位置之间的最大间隔，就是最大匹配子串长度
func longestValidParenthesesV2(s string) int {
ans := 0
stack := intstack{}
for i := 0; i < len(s); i++ {
if s[i] == '(' {
stack.Push(i)
continue
}
if s[i] == ')' {
top := stack.Top()
if top == -1 || s[top] == ')' {
stack.Push(i)
continue
}
stack.Pop()
}
}
// 如果遍历完栈为空，则原字符串长度即为所求
if stack.Top() == -1 {
return len(s)
}
// 初始end指针指向字符串末尾+1，便于计算
end := len(s)
for {
begin := stack.Pop()
if begin == -1 {
// 如果已无元素，需要check下最后弹出的位置之前的字符串长度是否是最大值，防止遗漏
if end > ans {
ans = end
}
break
}
tmpans := end - begin - 1
if tmpans > ans {
ans = tmpans
}
end = begin
}
return ans
}
type intstack struct {
list []int
}
func (s *intstack) Push(item int) {
s.list = append(s.list, item)
}
func (s *intstack) Pop() int {
if len(s.list) == 0 {
return -1
}
ans := s.list[len(s.list)-1]
s.list = s.list[:len(s.list)-1]
return ans
}
func (s *intstack) Top() int {
if len(s.list) == 0 {
return -1
}
return s.list[len(s.list)-1]
}