☆打卡算法☆LeetCode 32、最长有效括号 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个字符串，找出最长有效的字符串的长度。”

题目链接：

来源：力扣（LeetCode）

链接：32. 最长有效括号 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

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

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

二、解题

1、思路分析

这个题可以使用动态规划思路解题。

定义dp[i]表示以下标i字符结束的最长有效字符串长度，因此左括号在dp中的值必定为0，那么只需要知道右括号在dp数组中的位置。

遍历字符串求解dp值，每两个字符检查一次，如果倒数第二个 ‘)’ 是一个有效子字符串的一部分（记作 sub_s ），对于最后一个 ‘)’ ，如果它是一个更长子字符串的一部分，那么它一定有一个对应的 ‘(’ ，且它的位置在倒数第二个 ‘)’ 所在的有效子字符串的前面（也就是 sub_s 的前面）。因此，如果子字符串 sub_s 的前面恰好是 ‘(’ ，那么我们就用 2 加上 sub_s 的长度（dp[i−1]）去更新 dp[i]。同时，我们也会把有效子串 “(sub_s )” 之前的有效子串的长度也加上，也就是再加上 dp[i−dp[i−1]−2]。

最后的答案即为 dp 数组中的最大值。

2、代码实现

代码参考：

public class Solution {
    public int LongestValidParentheses(string s) {
            int left = 0, right = 0, ans = 0;
            int n = s.Length;
            for (int i = 0; i < n; i++)
            {
                if (s[i] == '(')
                    left++;
                else
                    right++;
                if (left == right)
                    ans = Math.Max(ans, right);
                else if (right > left)
                    left = right = 0;
            }
            left = right = 0;
            for (int i = n-1; i >=0; i--)
            {
                if (s[i] == '(')
                    left++;
                else
                    right++;
                if (left == right)
                    ans = Math.Max(ans, left);
                else if (left > right)
                    left = right = 0;
            }

            return ans * 2;
    }
}

3、时间复杂度

时间复杂度 ： O(n)

其中n为字符串的长度，只需要遍历一遍字符串即可求出dp数组。

空间复杂度： O(n)

我们需要一个大小为n的dp数组。

三、总结

这道题很适合用动态规划来解题，因为有最长这个字眼，用动态规划解这道题，需要先确定状态。

然后根据状态转移方程，根据初始条件和边界去实现过程。

需要注意的是计算顺序。