坑题—最长有效括号

发布: 分类: 评论次数： 阅读次数： 本文字数： 2.2k

别再问我为啥这几天疯狂写博客了，其实上也算不上是写博客吧。一方面主要是想给自己增加点记忆，对大佬的做法能掌握的更熟点，理解的更透测点；另一方面是想给以后的自己看看以前的他是多么的傻

今天想讲的是一道关于查找有效括号的最长长度问题，说之前，我还是得吐槽一下我自己，为啥我这么笨，，这么多的题都不会写

题目介绍

给定一个只包含’(‘和’)’的字符串，找出最长有效的括号子串长度（必须连续，格式正确）

举例如下：

1
2
3
4
5
6
7
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

我的思路

一开始，我看这题竟然还是个困难题，心想，我去，现在困难题都这么简单了么，直接上手就是一顿操作，提交，结果傻眼了。后来仔细一看，原来我写的是求有效括号数（想撞墙）。

接着，就是直线思路：既然是跟括号有关，那肯定逃不了栈的使用啊，接着就是噩梦的起点，我一直尝试将字符串中的字符，是(就入栈，)则讨论分析，一眼看起来也没啥问题对吧，正常人不都这么想的嘛（可能世界上就我一个不正常人）。但是对于是)的情况我怎么都分析不出来，首先，)肯定是需要将栈顶的(弹出，并且计数，但是怎么判断是最大的长度呢？栈空就是嘛？显然不行，因为可能栈永远也没法空，只要第一个是(且无法匹配就行。

既然这样，又该怎么办呢？那就直接判断栈要么为空或者栈底为(时，就将目前的计数和之前的最大值中选择一个赋给最大值；接着，又出现了一个问题，字符串中间出现)无法匹配怎么办，这时计数肯定是需要暂停的，从无法匹配的字符下一个字符继续（但是事实上，这是没法判断的，因为我们对)字符的处理是不入栈，只是和栈顶比较>）

所以说，目前的问题就是：存在不匹配的(，肯定会在栈底累积，不匹配的)无法处理，判断倒是可以，直接利用当前栈顶是否存在(即可，没有表示无法匹配（写到这里，我竟然还对自己的思路抱有侥幸心理，又去试了一次）

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
public int longestValidParentheses(String s){
    char[] s1 = s.toCharArray();
    if(s==null || s.length()==0){
        return 0;
    }
    Stack<Character> stack = new Stack<>();
    stack.push('#');
    int max = 0;
    int ans = 0;
    for(int i=0;i<s1.length;i++){
        if(s1[i]=='('){
            stack.push(s1[i]);
        }else{
            stack.pop();
            if(stack.empty()){
                stack.push(s1[i]);    //表示是未匹配成功的右括号
                max = 0;
                
            }else{
                max += 2;
                if(max>ans){
                    ans = max;
                }
            }
        }
    }
    return ans;
}

结果发现，，我对无法匹配的左括号没法处理，因为我无法判断一个左括号是否能被匹配，以至于我不知道代码里的max在栈内还有左括号的时候该不该赋为0（进行下一轮计数，被隔断了）

于是，我针对左括号无法判断是否可以匹配这个问题，使出了大招，没错，就是再写个函数用来判断从当前i（左括号）处，向后遍历，用一个新的栈操作（懂了吧，不懂？看代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if(s1[i]=='('){
    stack.push(s1[i]);
    //判断左括号是否能被匹配
    if(!left_is_ok(s1,i)){
      max = 0;
    }//无法匹配
}

private boolean left_is_ok(char[] s, int k){
  Stack<Character> stack = new Stack<>();
  for(int i=k;i<s.length;i++){
    if(s[i]=='('){
      stack.push(s[i]);
    }else{
      stack.pop();
      if(stack.empty()){
        return true;
      }
    }
  }
  return false;
}

懂了吧。。。。

虽然是通过了，但是，，结果却惨不忍睹：

（各路大佬别笑）

大佬思路1

依旧是利用栈，但是这个栈里存的不是s中的左右括号，而是括号的下标，这样就可以直接利用下标值计算长度了，说再多不如举个例子：

首先先初始化栈，需要在栈底添加一个可以区别任何其他字符的下标（-1），这样做的原因是因为在匹配中如果存在右括号不匹配，意思就是说栈里没有左括号与其匹配了，那接下来后面的子串里的有效序列我们就没法计算长度了（因为这个有效子串的开始下标是多少我们没有记录—开始下标也就是无法匹配的右括号下标），注意：一般的右括号我们是绝对不入栈的，只有无法匹配的才会入栈

比如说：(()))()，下标4的)则无法匹配，执行流程如下：

(：0入栈

(：1入栈

)：2，栈顶出栈，计算长度max = 当前的i减去栈顶index(注意，不是刚才出栈的，是出栈后的栈顶) = 2

)：3，栈顶出栈，计算长度max，这时发现栈空了，因此我们需要在栈底初始化时放个-1，这样，max = 3 - (-1) = 4

)：4，栈顶出栈（此刻栈里只有个-1，因此出栈），发现栈底是空的，表示这个右括号无法匹配，所以直接将该右括号的4 入栈代替之前的-1

(：5，入栈

)：6，出栈（此刻栈里只有4），计算max = Math.max(max,6-4) = 4

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int longestValidParentheses(String s){
    if(s==null || s.equals("") || s.length()==1){
        return 0;
    }
    char[] s1 = s.toCharArray();
    Stack<Integer> stack = new Stack<>();
    int max = 0;
    stack.push(-1);
    for(int i=0;i<s1.length;i++){
        if(s1[i]=='(') {
            stack.push(i);
        }else{
            stack.pop();
            if(stack.empty()){
                stack.push(i);      //表示只有右边，永远不会被匹配到
            }else{
                max = Math.max(max, i - stack.peek());
            }
        }
    }
    return max;
}

这个思路里，比较精彩的地方有：在栈底一开始放个-1，用来判断右括号的无法匹配，只有当栈里只有-1，且当前字符是)，出栈才会造成栈空，这时便让这个)的下标代替-1，继续判断其他右括号，同时可以用来计算这个无法匹配)后面的子串里的有效括号长度（作为开头）

大佬思路2

这个思路，怎么说呢，真的是很难想到，如果我不是看了解析，我可能想破头也不会往这方面去想

思路大概上是这样的，将无法匹配的字符全部标记为1，能匹配的全部标记为0（利用栈很容易实现），标记完后，就是计算最长的0序列的长度

至于，代码就靠大家自己去写啦

大佬思路3

看了这个大佬的思路后，我才发现原来这是一道dp问题，气的我啊，都想撞墙

首先定义dp数组，dp[i]表示以下标为i的字符结尾的有效括号的最长长度（注意理解，举个例子，())，这里的i=2时，dp[2]=0）

遍历s字符串

  1. 如果当前字符为(，则直接dp设置为0
  2. 如果为)，则需要判断；如果i-1为(，则刚好可以与i处的)匹配，则dp[i] = dp[i-2] + 2；如果i-1为)，则需要往前查找，假设i应该匹配的位置是j，则j = i-1-dp[i-1]，如果j处为)，则直接dp[i] = 0，否则，dp[i] = dp[j-1] + dp[i-1] + 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
26
27
28
29
30
31
32
33
34
35
36
37
38
public int longestValidParentheses(String s){
    if(s.length()==0 || s.length()==1){
        return 0;
    }
    int[] dp = new int[s.length()];
    Arrays.fill(dp,0);

    char[] s1 = s.toCharArray();
    if(s1[1]==')' && s1[0]=='('){
        dp[1] = 2;
    }

    for(int i=2;i<s.length();i++){
        if(s1[i]==')'){
            //判断s1[i-1]
            if(s1[i-1]=='('){
                dp[i] = dp[i-2] + 2;
            }else{
                int j = i - 1 - dp[i-1];
                if(j>0 && s1[j]=='('){
                    dp[i] = dp[j-1] + dp[i-1] + 2;
                }else if(j==0 && s1[j]=='('){
                    dp[i] = dp[i-1] + 2;
                }
                else{
                    continue;
                }
            }
        }
    }
    int ans = 0;
    for(int i=0;i<dp.length;i++){
        if(dp[i]>ans){
            ans = dp[i];
        }
    }
    return ans;
}

结束

唉，难受啊，每次都能在评论区看到和我同病相怜的，怀疑自己的脑袋是怎么长的，希望下一次的博客是很久之后了（并且会是一部关于番剧的文章）

偷偷的告诉你们，，，我最近在追番哦，名字嘛，“女神宿舍的宿管君”以及“进化果实～不知不觉踏上胜利的人生～”，等看完了就写，别急～