前言

---

最近刷LeetCode，遇到一个题目感觉挺有意思：

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

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

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

题目中让求解一串字符中所有含有效括号子串的最大长度，所谓有效括号示例中没说明完全，其实还有一种情况就是(())()括号相互包含以及并列的情况。

刚开始看到题目也是有点蒙，因为似乎不能用一般的穷解法来进行抽象(穷解法最佳代表：冒泡排序和选择排序，23333)，俗话说的好，遇事不绝穷举法！(其实算法优化也可以看作是让计算机以更快的时间拿到所有符合规范的结果，广义上的穷举)，这可咋个搞？

最后使用了递归和栈两种方法来解决。

解题思路1：递归

---

递归的概念

一种便于理解的心理模型是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这时你已经知道该怎么做的。

斐波那契函数属于典型的递归问题：

function fn(n) {
  if (n == 0 || n == 1)
    return n
  
  return fn(n-1) + fn(n-2)
}

题目分析

1. 求解所有包含有效括号子串时可以从最短有效括号"()"开始然后同时从左括号和右括号开始自底向上往两边匹配字符串，每一次匹配之后判断有没有相邻有效括号字串，如果有就合并两个子串
2. 由于无法预知所有匹配情况，在每次子串向外扩张匹配和合并子串时，都需要进行再次判断，需要对所有可能的子问题进行递归处理求解

题解图示

题解算法

/**
 * @param {string} s
 * @return {number}
 */
function longestValidParentheses(s) {
  var matchArray = [];
  var done = false;
  var i = 0;
  var maxLength = 0;

  /* 获取所有()的位置索引 */
  for (i; i < s.length - 1; i++) {
    if (s[i] === '(' && s[i + 1] === ')') {
      matchArray.push([i, i + 1]);
      i++;
    }
  }
  
  /* 合并相邻有效括号数组 */
  var doConcat = function() {
    var find = false;
    for (i = 0; i < matchArray.length - 1; i++) {
      if (matchArray[i][matchArray[i].length - 1] + 1 === matchArray[i + 1][0]) {
        find = true;
        matchArray[i] = matchArray[i].concat(matchArray[i + 1]);
        matchArray.splice(i + 1, 1);
        i--;
      }
    }
    if (find) doConcat();
  };

  while(!done) {
    doConcat();
    done = true;
    matchArray.map(function(item) {
      // 经匹配括号从内至外扩张合并新的有效括号
      if (s[item[0] - 1] === '(' && s[item[item.length - 1] + 1] === ')') {
        item.unshift(item[0] - 1);
        item.push(item[item.length - 1] + 1);
        done = false;
      }
      maxLength = Math.max(item.length, maxLength);
    });
  }

  return maxLength;
};

解题思路2：栈和回溯

---

栈的概念

堆栈的基本特点：

• 先入后出，后入先出的数据结构。
• 除头尾节点之外，每个元素有一个前驱，一个后继。

题目分析

1. 确定限制条件
   一个有效括号子串至少需要包含左括号和右括号两个字符’()'，且多个有效括号具有包含关系或相邻关系

2. 分析限制条件
   分析条件，相邻关系很好判断，只要第n个括号和第n+1个括号能匹配就满足了，已经满足匹配的字符对可以从回溯范围中去掉(剪枝)。包含关系诸如’((()))‘这种，其实可以借助栈这种数据后入先出的存储结构，先存储连续的’(‘，当尝试访问的下一个字符与栈顶字符’('满足匹配关系时，将栈顶字符弹出，以便判断接下来的字符与栈顶字符的匹配情况。

3. 减少查找路径
   在左到右搜索整个字符串的过程中，我们需要存储已经搜索过的字符，因为无法预知接下来未遍历的字符的匹配情况。但我们是不是需要存储所有已经遍历过的字符呢？不是，只需要存储接下来可能形成匹配结构的已遍历字符，不具有形成可匹配字符可能性的字符会被过滤掉，比如如果第一个字符是’)'，那么之后无论出现哪种括号，都无法与这个字符形成有效匹配字符了，所以这个字符就需要过滤掉。

4. 确定回溯范围
   以上第2点提到的用于存储已经遍历过的字符存储结构即为回溯范围，且这个回溯范围动态变化。

5. 确定回退点
   向右搜索选择时如果下一个字符与栈顶字符存在有效括号匹配，那么表明我们已经找到另一个匹配情况但是还可能找到更多匹配情况，所以需要回退回到上一个点(下图中执行stack2.pop())，回退时根据记录的字符索引计算当前已经连续匹配的有效括号字符的长度，最后记录有效括号字符长度的最大值即可。

题解图示

• stack1 – 栈1用于存储所有遍历过的并且存在匹配可能性的左括号(回溯范围)
• stack2 – 栈2用于存储所有栈顶字符的’索引值-1’
• 红色方块 – 连续有效字符匹配中断的情况
• 绿色方块 – 向回溯范围中存入的各个可回溯点
• 蓝色方块 – 执行回溯
• MAX – 有效括号字符长度的最大值

题解算法

/**
 * @param {string} s
 * @return {number}
 */
function longestValidParentheses(s) {
  var indexArray = [-1]; //动态存储左括号索引值，
  var maxLength = 0;
  var stack = []; // 栈存储已经遍历的左括号索引
  var i = 0; // 头指针

  for (i; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i);
    } else {
      if (stack.length) {
        // 括号匹配的情况从栈顶弹出
        tmp = stack.pop();
        // 索引数组同步弹出(至少保留一个索引)
        if (indexArray.length > 1) indexArray.pop();
        // 栈不为空，则将栈顶索引(尾指针)存入索引数组以便之后回溯计算最大字符串长度
        if (stack.length) indexArray.push(stack[stack.length - 1]);
        maxLength = Math.max(maxLength, i - indexArray[indexArray.length - 1]);
      } else {
        // 首个匹配到的字符为')'的非法情况，重置尾指针
        indexArray = [i];
      }
    }
  }

  return maxLength;
};

结语

---

本题中虽然栈的解法图示很长，但是相比递归解法，时间和内存消耗都更少，时间复杂度O(n)，空间复杂度为O(2n)。

⇸⇸ 阅读量： [ loading ]⇷⇷

---

• ← Previous Post
• Next Post →

---