一道 LeetCode 的多种解法，打消了我的自以为是！

雨点打透心脏的1/2处 2023-06-28 11:17 17阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![format_png][]

Leetcode 最新上线了手机版 APP，今天蹲坑的时候随手翻了一道题，一道和 **栈** 有关的题目，大概知道了解题思路，就点开了题解准备看看别人是如何写代码的，没想到最后一种解法让我感觉自己的智商受到了碾压。

#### 最长有效括号：https://leetcode-cn.com/problems/longest-valid-parentheses/ ####

## 题目描述 ##

给定一个只包含 `'('`和`')'` 的字符串，找出最长的包含有效括号的子串的长度。

**示例 1:**

输入: "(()"
    输出: 2
    解释: 最长有效括号子串为 "()"

**示例 2:**

输入: ")()())"
    输出: 4
    解释: 最长有效括号子串为 "()()"

##     ##

## 题目解析 ##

### 解法一：栈 ###

一开始看到这个题目，有点熟悉的感觉：相当于是 LeetCode 第 20 题 **有效的括号** 的升级版。

想到这立马尝试借助 **栈** 这个数据结构去解决。

> 括号相关的问题首先可以尝试使用 **栈** 这个数据结构去解决，至于原因，想一想应该不难理解，如果进来一个右括号，也就是 ')'，它会和之前 **最后一次遍历到的左括号** 匹配，栈的 **先进后出** 的特性保证了这一要求。

对于这道题目，因为我们要求的是子串的长度，因此我们可以考虑在栈中保存 *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;
    }

### 动画理解 ###

### 解法二：动态规划 ###

如果用 **栈** 来解决的话，这道题思路差不多就是这样。考虑到前不久一直聊 **动态规划**，于是试了一下用把它归纳到 **序列型动态规划** 来求解。

[动态规划之空间优化与总结回顾][Link 1]

我们可以定义 **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)，解法也有相似之处，只是说切题点不一样。

![format_png 1][]

正当我美滋滋时，突然看到另外一种解法，让我感觉自己的智商受到了碾压：**不需要额外的空间**，空间复杂度是 O(1) ！

### 解法三：借助变量 ###

使用了两个变量 Left 和 Right，分别用来记录到当前位置时左括号和右括号的出现次数。

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

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

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

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

### 代码实现 ###

//代码来源：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode/
    
    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;
        }
    }

### 动画理解 ###

**注意：****视频有背景音乐**

事实上，我在利用解法一求解完这道题目后还怡然自得，认为这道题目最简单的解法就是借助栈这种数据结构，没想到还有解法三这么巧妙的解法。。。

**-----------------------**

**公众号：五分钟学算法****（ID：CXYxiaowu****）**

**博客：www.cxyxiaowu.com**

**知乎：程序员吴师兄**

**一个正在学习算法的人，致力于将算法讲清楚！**

长按下图二维码关注，和你一起领悟算法的魅力**。**

![format_png 2][]

**戳一下下方的小程序，24 小时一起学算法**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA?x-oss-process=image/format,png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e6159cd79e84fc5b50aae5a7d874e8cb927f3689ba513616b35dff38440e3b5efda9b4235&idx=2&mid=2247487192&scene=21&sn=86ea2be7047d8817e9c201a93abc6737#wechat_redirect
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9VMnpuTTRpY0RFQTVMUkVqb09MQjFVQ0c3NERRbXRic1VtaG1QMGdNRXQ5ZlFYSkpEamljcG5GVVFBR29hWGIzRm9kMm04WnN5Tk0yTmJHdWR6Rnk4ZFVRLzY0MA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA?x-oss-process=image/format,png