前端刷题路-Day59：最长有效括号（题号32）

这是我参与更文挑战的第23天，活动详情查看： 更文挑战

最长有效括号（题号32）

题目

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

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
复制代码

示例 2：

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

示例 3：

输入：s = ""
输出：0
复制代码

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

链接

leetcode-cn.com/problems/lo…

解释

这题啊，这题重在思路。

笔者自己是没有想到什么思路的，也知道有一种解法是DP，但这里就是想不出来，也是没有办法，可能还是解决的问题不够多吧。

官网给出了三种答案，笔者这里记录下前两种吧，第三种有点过于复杂，就算看懂了后续可能也记不住，也就不浪费时间了。

首先是栈操作，这一点和别的括号问题十分类似，不过需要有个垫底的元素，或者叫做占位元素也可以。

栈的基本逻辑还是和之前一样，遇到(就推入栈，遇到)就抵消栈的最后一个元素。这里需要注意，入栈的元素是index。

用index就会带来一个问题，比方说这样的一个?：

"()"
复制代码

如果单纯的推入栈抵消栈，那么栈内的元素会是这样的?：

[0, 1]
复制代码

在推入)括号的时候，当前的index是1，但长度是2，要怎么拿到正确的长度呢？

第一时间的思路有两种：

1. 1 - 0 + 1

   这种思路很简单，差一个位置就补一下，解决当前的情况是没有问题的。

2. 在栈前面在插入一个-1，用当前的index减去栈尾的元素值

   用了这种思路后栈就会变成这样?：

   [-1, 0]
   复制代码

   当遇到)时，会和0进行抵消操作，此时栈尾的元素就变成了-1，此时的index是1，所以长度就是1 - -1，得到2。

既然有两种思路，那么用那种方式比较好呢？别急，让我们看看另外一种情况?：

"())()()"
复制代码

首先，如果使用第一种思路，这题就GG，原因很简单，在index为2的时候断开了，此时栈为空。

在继续插入时，插入的结果为?：

[3, 4]
复制代码

在这一步，依然可以用4 - 3 + 1来得到正确的长度，可是后面的两个怎么办呢？因为后面是?：

[5, 6]
复制代码

如果只靠自己得到的长度只能是2，显然是不对的，所以必须借助一个新的变量来暂时存储前面的长度，遇到断开的情况就重置为0，如果不断开就就继续加，也是可以的，除了比较麻烦没什么缺点。

如果使用第二种方案呢？相对就比较简单了。

在index为2时，将-1抵消掉了，那么此时栈空了，空了的时候就将当前index推入栈，作为一个垫底值，所以此时的栈是这样的?：

[-1]			// ""
[-1, 0]			// "("
[-1]			// "()"
[2]			// "())"
复制代码

之后再往里推入(，后序遇到)括号抵消，栈里面又只剩2了，再遇到下一对括号，此时)的index为6，减去栈尾的元素2，得到的结果就是4了。

看下整体流程?：

由此可得最后的最大值是4，相比思路1少了一个存储当前进度的变量，而且思路更为清晰。

DP的解法就放到答案里去了，内容太多可能会出现看了前面的忘了后面的情况。

自己的答案

无

更好的方法（栈）

var longestValidParentheses = function(s) {
  var stack = [-1]
      max = 0
  for (let i = 0; i < s.length; i++) {
    var char = s[i]
    if (char === '(') {
      stack.push(i)
    } else {
      stack.pop()
      if (stack.length) {
        max = Math.max(i - stack[stack.length - 1], max)
      } else {
        stack.push(i)
      }
    }
  }
  return max
};
复制代码

这就是解释里说的的思路了，此处的实现比较简单，重点就在于栈空了的时候，要把当前index推入栈中。

更好的方法（动态规划）

DP说简单也简单，说复杂也有点复杂。

由于是只需要查看最长的长度，所以DP只需要一个一维数组，这没啥可说的。

重点需要考虑的就是DP[i]和之前的关系，下面按照情况的不同分析下?：

• 当前元素是(

  由于当前元素无法组成新的封闭括号，所以只需要考虑前一个元素的最长的有效括号就好?：

  dp[i] = dp[i - 1]
  复制代码

• 当前元素是)

  • 前一个元素是(

    这就直接组成新的封闭括号了，所以只需要拿到i - 2的值，加上2就好了。

    dp[i] = (dp[i - 2] || 0) + 2
    复制代码

  • 前一个元素是)

    那么现在我们就有两个)了，所以需要找到两个(来进行匹配。

    但仔细一想其实不需要，因为前一个(的最长有效括号已经有值了，那就是dp[i - 1]。

    所以现在需要考虑的就是当前的)到底有没有对应的(来进行匹配。

    那去哪里找呢？

    我们需要跨过前一个元素的最大有效长度，也就是dp[i - 1]，也就是需要判断s[i - dp[i - 1] - 1]是不是)

    • 如果是(，那就证明可以组成完整的括号。

      并且此时需要加上(前面的最大长度，虽然有可能不存在，不存在给0就好了。

    • 如果不是(，那就不用管了，因为没法组成有效的括号，放弃。

在理清楚这个逻辑之后，代码就很简单了?：

var longestValidParentheses = function(s) {
  var len = s.length
      dp = new Array(len).fill(0)
  for (let i = 0; i < len; i++) {
    if (s[i] === ')') {
      if (s[i - 1] === '(') {
        dp[i] = (dp[i - 2] || 0) + 2
      } else if (s[i - dp[i - 1] - 1] === '(') {
        dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] || 0)
      }
    }
  }
  return Math.max(...dp, 0)
};
复制代码

实现起来比较简单，重点就是逻辑是否能理清楚，能理清楚就完全不用担心了，如果看不懂就多看几次了，这里的抽象逻辑确实比较绕。

PS：想查看往期文章和题目可以点击下面的链接：

这里是按照日期分类的?

前端刷题路-目录（日期分类）

经过有些朋友的提醒，感觉也应该按照题型分类
这里是按照题型分类的?

前端刷题路-目录（题型分类）

有兴趣的也可以看看我的个人主页?

Here is RZ