政子的博客

技术|学习|随笔

LeetCode-Longest Valid Parentheses

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

第一个办法是暴力查找，时间复杂度是 O(n^3)，空间复杂度是 O(1)。主要方法是不断测试偶数个长度的括号是否匹配。

结果显而易见地超时了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func longestValidParentheses(s string) int {
    maxLen:=0
    for i:=0;i<len(s);i++ {
        step:=2
        if maxLen>step {
            step=maxLen
        }
        for j:=i+step;j<=len(s);j+=2 {
            leftNum:=0
            isValid:=true
            for k:=i;k<j;k++ {
                if s[k]=='(' {
                    leftNum++
                }else if leftNum>0 {
                    leftNum--
                }else{
                    isValid=false
                    break
                }
            }
            if leftNum>0 {
                isValid=false
            }
            if isValid && j-i>maxLen {
                maxLen=j-i
            }
        }
    }
    return maxLen
}

Solution 中提供了一种 DP 解法，非常巧妙。DP 算法的效率非常高，只需要 O(n)的复杂度即可计算完毕。

在这个算法中，dp[i]代表在字符串第 i 个字符之前有多少个敛许配对的括号。而算法中最难的是，如何寻找递推公式，也就是如何推出 dp[i]的值。

因为左括号的出现并不能说明任何有关配对的信息，所以必须先考虑右括号，在考虑前面配对的左括号。所以，在 dp 数组中，左括号对应的配对值都为 0。所以，有关 dp[i]的值，这里要根据右括号和它之前的括号类型分两种情况讨论。

  1. s[i]==')' && s[i-1]=='('

    这种情况没什么好说的，就是连续配对的括号，直接就可以被当作一对，所以直接在前面配对个数的基础上+2。

    dp[i]=dp[i-2]+2

  2. s[i]==')' && s[i-1]==')' && s[i-dp[i-1]-1]=='('

    这种情况不容易一下子想到。当出现连续的两个右括号的时候，如果要配对，那就说明在前面某个地方会有配对的左括号。所以就需要确定左括号出现的位置。在 i 之前的位置中，很可能会有已经配对好的括号，所以必须要跳过这些括号，找到最外层的左括号。这时候，dp[i-1]就可以给我们有关前面有几个连续配对括号的信息了。所以只需要减去它，便可以得到最外层没有配对的左括号必须要出现的位置。所以：

    dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func longestValidParentheses(s string) int {
    maxLen:=0
    dp:=make([]int,len(s))
    for i:=1;i<len(s);i++ {
        if s[i]==')' {
            if s[i-1]=='(' {
                if i>=2 {
                    dp[i]=dp[i-2]+2
                }else{
                    dp[i]=2
                }
            }else if i-dp[i-1]>0 && s[i-dp[i-1]-1]=='(' {
                if i-dp[i-1]-2>=0 {
                    dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2
                }else{
                    dp[i]=dp[i-1]+2
                }
            }
            if dp[i]>maxLen {
                maxLen=dp[i]
            }
        }
    }
    return maxLen
}

Solution 中的第三种方法是通过栈，复杂度同样是 O(n)。

这个思路也十分的巧妙（我最开始怎么就没想到呢）。通过将 index 推入栈中来记录该括号在字符串中的位置，然后使用验证字符串匹配的方法进行匹配，匹配到后，立即计算匹配得到的长度，并更新最大长度。如果没有匹配成功，就直接推入栈中，作为垫脚（为了帮助下次匹配成功的时候计算长度）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func longestValidParentheses(s string) int {
    maxLen:=0
    stack:=make([]int,0)
    stack=append(stack,-1)
    for i,c:=range s {
        if c=='(' {
            stack=append(stack,i)
        }else{
            stack=stack[:len(stack)-1]
            if len(stack)==0 {
                stack=append(stack,i)
            }else{
                if l:=i-stack[len(stack)-1];l>maxLen {
                    maxLen=l
                }
            }
        }
    }
    return maxLen
}

Solution 中的最后一种方法是进行两次扫描，这个方法比较玄妙，时间复杂度不变，为 O(n)，但是空间复杂度从前面题目中的 O(n)下降到了 O(1)。

我认为这样做将两个括号配对进行了简化，不论两个括号中间间隔了几个，只要可以配对，就一定会有l==r。如果没配对成功，要么 r>l，要么到了末尾，依旧是l<r，所以根据这些规律就可以得到究竟有多少括号配对。

至于为何还要从右往左扫描，这是因为有可能左边从左括号的个数会影响右边的配对情况，如果反过来扫描，就可以避免计数器被左边多余的括号影响，反之亦然。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func longestValidParentheses(s string) int {
    l,r,ret:=0,0,0
    for _,c:=range s {
        if c=='(' {
            l++
        }else{
            r++
        }
        if l==r && ret<2*l {
            ret=2*l
        }else if r>l {
            l=0
            r=0
        }
    }
    l=0
    r=0
    for i:=len(s)-1;i>=0;i-- {
        c:=s[i]
        if c=='(' {
            l++
        }else{
            r++
        }
        if l==r && ret<2*r {
            ret=2*l
        }else if l>r {
            l=0
            r=0
        }
    }
    return ret
}