算法：最长有效括号

一时失言乱红尘 2023-07-05 10:23 18阅读 0赞

题目描述：  
给定一个只包含 ‘(‘和’)’ 的字符串，找出最长的包含有效括号的子串的长度。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70]  
方法一：栈  
括号相关的问题首先可以尝试使用 栈 这个数据结构去解决，至于原因，想一想应该不难理解，如果进来一个右括号，也就是 ‘)’，它会和之前 最后一次遍历到的左括号 匹配，栈的 先进后出 的特性保证了这一要求。  
对于这道题目，因为我们要求的是子串的长度，因此我们可以考虑在栈中保存 index，这样子我们不仅可以通过 index 找到对应的括号，还可以借此来求长度，我们的思路可以分为下面几步：  
1、从左到右遍历输入的字符串

2、如果遇到的是 ‘(’，意味着这并不能和前面遍历过的部分组成合法答案，此时我们只需要把当前 index 入栈即可

3、如果遇到的是 ‘)’，这时我们就要看栈顶保存的元素了，这里就会有几种情况：

栈顶保存的是 ‘(’，表示当前元素和栈顶元素可以配对，这个时候我们需要把栈顶元素弹出栈，记录答案则记录当前 index 和弹出配对元素后的新栈顶 index 之间的距离，这个地方是重点，如果不理解，你可以思考下面两个例子：  
“((()()”  
“((())”  
栈顶保存的是 ‘)’，如果是这种情况，表示前面没有可配对的 ‘(’，我们此时还是需要把当前 index 入栈，原因是

我们确定距离需要知道边界，如果不理解，还是有两个例子供你参考：  
“))(())”  
“())()()”  
栈是空的，当然在第一种情况中，你弹出栈顶元素后也会使得栈变空，为了避免这种情况，我们可以在最开始的时候推一个 -1 入栈，这样可以节省我们的判断次数，并且当栈中的没有元素的时候，我们也可以用这个 -1 来计算当前子串的长度，你可以参考下面这两个例子：  
“()”  
“()(())”

public int longestValidParentheses(String s) { 
        if (s == null || s.length() == 0) { 
            return 0;
        }
    
        int n = s.length();
    
        char[] sArr = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
    
        int result = 0;
    
        // -1 入栈用于处理边界条件
        stack.push(-1);
    
        for (int i = 0; i < n; ++i) { 
            // stack.size() > 1 表示栈不为空，而且我们必须保证栈顶元素是 '('
            if (sArr[i] == ')' && stack.size() > 1 && sArr[stack.peek()] == '(') { 
                // 配对的 '(' 出栈
                stack.pop();
                // 记录长度
                result = Math.max(result, i - stack.peek());
            } else {  // 其他情况，直接将当前位置入栈
                stack.push(i);
            }
        }
    
        return result;
    }

方法二：  
动态规划  
我们可以定义 dp\[i\] 表示的是 str\[0…i\] 的答案，思路其实和前面很类似：

1、从左到右遍历输入的字符串

2、如果遇到的是 ‘(’，意味着这并不能和前面遍历过的部分组成合法答案，因为 dp 状态数组中记录的是答案，这个时候说明 dp\[i\] = 0，也就是不用做任何记录

3、如果遇到的是 ‘)’，这时我们还是需要往前看：

如果 str\[i - 1\] 是 ‘(’，那么 dp\[i\] = dp\[i - 2\] + 2  
如果 str\[i - 1\] 是 ‘)’，这表示 str\[i - 1\] 已经配对了，因此我们还要继续往前看，从当前位置往左，看第一个没有被配对的 ‘(’，怎么找这个位置呢，这里我们就可以利用 dp\[i - 1\] 这个信息，dp\[i - 1\] 表示的是之前匹配的长度，那么 ：  
i - dp\[i - 1\] - 1 表示的就是从当前位置往左，第一个没有被配对的位置  
如果位置 i 和 位置 i - dp\[i - 1\] - 1 配对后，我们可以看看当前的序列是否可以和之前匹配的序列链接起来，也就是加上 dp\[i - dp\[i - 1\] - 2\]

public int longestValidParentheses(String s) { 
        if (s == null || s.length() == 0) { 
            return 0;
        }
    
        int n = s.length();
    
        char[] sArr = s.toCharArray();
    
        int[] dp = new int[n];
    
        int result = 0;
        for (int i = 1; i < n; ++i) { 
            if (sArr[i] == ')') { 
                // 如果前一个位置是 '('，直接配对
                if (sArr[i - 1] == '(') { 
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } 
                // 前一个位置是 ')'
                // 我们从当前位置往左看，如果第一个没有被匹配的位置是 '('
                // 表明当前位置是可以被匹配的
                else if (i - dp[i - 1] - 1 >= 0 && sArr[i - dp[i - 1] - 1] == '(') { 
                    // 这里其实是 dp[i] = i - (i - dp[i - 1] - 1) + 1 = dp[i - 1] + 2
                    // 但是我们还需要考虑之前的答案，也就是 dp[i - dp[i - 1] - 2]
                    // 首先判断 i - dp[i - 1] - 2 是否越界
                    // 如果没有越界就将其加上
                    dp[i] = dp[i - 1] + 2;
    
                    if (i - dp[i - 1] >= 2) { 
                        dp[i] += dp[i - dp[i - 1] - 2];
                    }
                }
    
                result = Math.max(result, dp[i]);
            }
        }
    
        return result;
    }

两种方法时空复杂度都是 O(n)，解法也有相似之处，只是说切题点不一样。  
方法三：  
不需要额外的空间，空间复杂度是 O(1)  
借助变量  
使用了两个变量 Left 和 Right，分别用来记录到当前位置时左括号和右括号的出现次数。

当遇到左括号时，Left 自增 1，右括号时 Right 自增1。

对于最长有效的括号的子串，一定是左括号等于右括号的情况，此时就可以更新结果 res 了，一旦右括号数量超过左括号数量了，说明当前位置不能组成合法括号子串，Left 和 Right 重置为 0。

但是对于这种情况 “(()” 时，在遍历结束时左右子括号数都不相等，此时没法更新结果 res，但其实正确答案是 2，怎么处理这种情况呢？

答案是再 反向遍历一遍 ，采取类似的机制，稍有不同的是此时若 Left 大于 Right 了，则重置 0，这样就可以涵盖所有情况。

public class Solution { 
        public int longestValidParentheses(String s) { 
            int left = 0, right = 0, maxlength = 0;
            for (int i = 0; i < s.length(); i++) { 
                if (s.charAt(i) == '(') { 
                    left++;
                } else { 
                    right++;
                }
                if (left == right) { 
                    maxlength = Math.max(maxlength, 2 * right);
                } else if (right >= left) { 
                    left = right = 0;
                }
            }
            left = right = 0;
            for (int i = s.length() - 1; i >= 0; i--) { 
                if (s.charAt(i) == '(') { 
                    left++;
                } else { 
                    right++;
                }
                if (left == right) { 
                    maxlength = Math.max(maxlength, 2 * left);
                } else if (left >= right) { 
                    left = right = 0;
                }
            }
            return maxlength;
        }
    }

示例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 7]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 8]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200214092940859.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200214093609729.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200214093654137.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200214093830406.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020021409390696.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020021409394933.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200214094025248.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2020021409404346.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200214094125948.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70