19 | 最小体力消耗路径：如何突破经典题型，掌握解题模板？

数据结构与算法面试宝典 - 前微软资深软件工程师 - 拉勾教育

数据结构与算法面试宝典 - 前微软资深软件工程师 - 拉勾教育

在本讲，我将带你继续探究 “一题多解”，结合前面学习过且面试常考的知识点，比如区间问题、双指针、动态规划、栈、贪心，从多个角度去求解一个题目，通过逐步分析已知条件、提取题目特点，进而将不熟悉的题目变成我们擅长求解的题目，最终攻克 “最长有效括号长度” 的难题。

在正式介绍前，我有两点说明。

1. 这类题目的解法非常多，但本讲仅重点介绍其中 5 种具有代表性的解法。目的是让你在算法面试时，能够展开更多的解题思路。
2. 并不是每种解法都能够利用常量空间，如果用到，我会特别注明。

题目

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

输入：s = “(()”

输出：2

解释：最长有效括号子串是 “()”

注意，“有效” 需要满足两个条件：

• 连续子串；
• 子串有效指的是每个左括号 ‘(‘ 都可以找到相应的右括号 ‘)’ 完成一一配对。

在 “01 | 栈：从简单栈到单调栈，解决经典栈问题” 的 “例 1” 中，我们介绍过如何判断一个字符串是否合法（即有效）。只不过，在这个题中，我们要从一个字符串中找到一个子串，需要满足 “最长且合法”。

当我们拿到题目，最容易想到的思路是：

• 一共有 O(N2) 个连续子串
• 判断每个连续子串是否合法

如果直接按上述思路开始进行暴力求解，那么时间复杂度就会上升到 O(N3)。因此，在求解前，我们应该根据已知条件，认真分析题目的特点，然后和暴力破解法 Say GoodBye。

合法字符串的特性

首先我们看一下合法字符串长什么样？有什么样的特点？一般而言，括号对匹配成功的合法字符串，有三种情况。

• 相连：指很多个配对成功的括号连在一起，比如 [“()”, “()()”, “()()()”]。
• 嵌套：指内外层层相套，但是它们能够合法配对成功，比如 [“()”, “(())”, “((()))”]。
• 相连 + 嵌套：指相连和嵌套混合的情况，但是它们是合法的字符串，比如 [“()(())”, “(())()”]。

注意，在后文中，我们将用 “相连”“嵌套”“相连 + 嵌套” 特指这三种情况。

特点 1： 区间

我们发现，括号能够配对的时候，总是有一个左括号 + 一个右括号，如果我们将左括号的下标当成一个区间的左端点，右括号的下标当成一个区间的右端点。

那么用区间来表示一个合法字符串，会得到什么有趣的特点呢？下面我们仍然从合法字符串的 3 种情况展开。

• 相连：比如 “()()()”，就可以得到区间 [[0,1], [2,3], [4,5]]。
• 嵌套：比如 “(())”，就可以得到区间 [[0,3], [1,2]]。
• 相连 + 嵌套：比如 “()(())”，就可以得到区间 [[0,1], [2,5], [3,4]]。

我们尝试定义一下区间的连接性。

如果两个区间 , 满足下面 2 个条件之一：

1. 有公共点，即 not ((b < c) || d < a) )；
2. b < c && b + 1 == c 或者 d < a && d + 1 == a。

我们就称这两个区间具有连接性。

我这里给出三个例子，帮你理清区间的连接性。

例 1：区间 [1,2], [3,4] 是否具有连接性？答案是！因为区间 [1,2] 的右端点 2 加上 1 就是区间 [3,4] 的左端点（满足条件 2）。

例 2：区间 [0,5] 和区间 [2,5] 是否具有连接性？答案是！因为它们是有公共点的，因此我们认为它们具有连接性。

例 3：区间 [0, 1] 和区间 [3,4] 则不具有连接性。因为这两个区间不满足条件 1，也不满足条件 2。

那么定义好区间的连接性之后，有什么用途呢？这样操作后，我们就可以把原始的题目分为两步：

1. 得到所有配对的左括号与右括号的下标；
2. 给定一系列区间，找到最长的区域，这个区域被具有相连性的区间覆盖。

针对第 2 步，我们进一步举例说明。

例 1：当给定的区间为 [1, 2], [3,4] 的时候，我们可以找到一个最长的区域 [1, 4]，这个区域是由具有相连性的两个区间覆盖的。

例 2：当给定的区间集合为 [0, 1], [3,4], [5,6], [6,9] 的时候，最长的区域为 [3, 9]。由 [3,4], [5,6], [6,9] 这三个具有相连性的区间覆盖。

注意，我们不要求区域内的区间两两满足相连性。

比如 [3,4] 和 [5,6] 具有连接性，但是 [3,4] 和 [6,9] 不具有连接性。在操作时，我们可以这样操作：

Step 1. [3,4] 和 [5,6] 具有连接性，合并成一个大区间 [3,6]；

Step 2. [3,6] 与 [6,9] 具有连接性，合并成一个大区间 [3,9]。

例 3：给定一个区间 [0, 1]，那么最长区域就是 [0, 1]。

注意：一个合法的括号配对字符串不会生成一个单独的很长的区间，比如 [0, 10]。如果 s[0]= ‘(‘ 与 s[10]=’)’ 配对成功，那么必然是一种嵌套的合法字符串，内部还会有很多区间必须要给出来。

第一步的处理，可以直接使用栈（参考 “01 | 栈：从简单栈到单调栈，解决经典栈问题” 的 “例 1”）。而第二步的处理需要用到贪心算法（参考 “11 | 贪心：这种思想，没有模板，如何才能掌握它？” 的 “例 2”）。

基于这样的思路，我们就可以写出代码如下（解析在注释里）：

class Solution {
public int longestValidParentheses(String s) {
final int N = s == null ? 0 : s.length();
    Stack<Integer> st = new Stack<>();
    List<int[]> ranges = new ArrayList<>();
for (int i = 0; i < N; i++) {
final char c = s.charAt(i);
if (c == ')') {
if (!st.isEmpty()) {
final int topIdx = st.pop();
          ranges.add(new int[]{topIdx, i});
        }
      } else {
        st.push(i);
      }
    }
    Collections.sort(ranges, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
      }
    });
int start = 0;
int end = -1;
int ans = 0;
for (int i = 0; i < ranges.size(); i++) {
final int from = ranges.get(i)[0], to = ranges.get(i)[1];
if (from <= end + 1) {
        end = Math.max(end, to);
      } else {
        start = from;
        end = to;
      }
      ans = Math.max(ans, end - start + 1);
    }
return ans;
  }
}

代码：Java/C++/Python

复杂度分析：从字符串中提取区间，只需要 O(N) 的时间复杂度。然后我们需要对区间进行排序，最差情况下有 O(N/2) 个区间，那么排序的时间复杂度会上升到 O(NlgN)。最后的贪心算法时间复杂度为 O(N)。因此，整个问题的时间复杂度为 O(NlgN)，空间复杂度为 O(N)。

关于求解最长相连通的区间问题，这里我还给你留了一个练习题。你可以做一做。

练习题 1：给定一系列区间，将重合的区间合并在一起。

输入：A = [[1,2], [2,3], [2,6], [7, 8]]

输出：[[1, 6], [7,8]]

代码：Java/C++/Python

我们发现，实际上整个问题的时间复杂度是由排序带来的，那么，有没有可能优化掉排序呢？我们先来看一下题目中生成区间的代码：

if (c == ')') {
if (!st.isEmpty()) {
final int topIdx = st.pop();
      ranges.add(new int[]{topIdx, i});
   }
}

不难发现，在右括号找到左括号匹配成功的时候，总是记录下左括号下标 <，右括号下标 >。

题目中，左括号的下标本来就是有序的，那么我们可以使用一个数组 pairPos[] 来记录这个匹配成功的区间信息。采用的原则如下：

pairPos[左括号的下标] = 右括号的下标
pairPos[右括号的下标] = -1

就是下图所示的样子：

也就意味着，我们将区间信息成对放在了 ，其中 i 是一个字符串中配对成功的左括号的下标。

那么，基于这个思想，我们可以优化代码如下（解析在注释里）：

class Solution {
public int longestValidParentheses(String s) {
final int N = s == null ? 0 : s.length();
    Stack<Integer> st = new Stack<>();
int[] pairPos = new int[N];
    Arrays.fill(pairPos, -1);
for (int i = 0; i < N; i++) {
final char c = s.charAt(i);
if (c == ')') {
if (!st.isEmpty()) {
final int topIdx = st.pop();
          pairPos[topIdx] = i;
        }
      } else {
        st.push(i);
      }
    }
int start = 0;
int end = -1;
int ans = 0;
for (int i = 0; i < N; i++) {
if (pairPos[i] == -1) {
continue;
      }
final int from = i, to = pairPos[i];
if (from <= end + 1) {
        end = Math.max(end, to);
      } else {
        start = from;
        end = to;
      }
      ans = Math.max(ans, end - start + 1);
    }
return ans;
  }
}

代码：Java/C++/Python

复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(N)。

接下来我们再看题目的另外一个特点，连续性。

特点 2：连续性

通过 “特点 1” 的分析，我们将问题处理成区间的连接性问题。不难发现，所谓相连性，就是要求：

求解出来的最长区间，里面的每个字符都可以配对成功。

那么，这个条件必然等价于，这个区间里面的下标，一旦排序之后，必然由相邻的整数构成。下面我们分别举例进行说明。

• 相连：比如 “()()()”，就可以得到区间 [[0,1], [2,3], [4,5]]。排序后，得到整数列表 [0,1,2,3,4,5]。
• 嵌套：比如 “(())”，就可以得到区间 [[0,3], [1,2]]。排序后，得到整数列表 [0,1,2,3]
• 相连 + 嵌套：比如 “()(())”，就可以得到区间 [[0,1], [2,5], [3,4]]。排序后，得到整数列表 [0,1,2,3,4,5]。

当找到一个不能匹配的位置 NOT 的时候，我们不可能在 NOT 的左边找一个位置 left_pos，在 NOT 的右边找一个位置 right_pos，并且使得 [left_pos, right_pos] 是一个合法的字符串。

上面描述的情况如下图所示：

我们可以使用反证法进行证明。

证明：假设存在一个位置 NOT，不能找到一个左括号与之匹配。但是我们可以找到 left_pos < NOT 和 right_pos > NOT，并且使得 [left_pos, right_pos] 是一个合法括号的字符串。

首先，由于 [left_pos, right_pos] 是一个合法的括号配对的子串，那么可以肯定，这个区间里面的每一个字符应该都有左括号与之匹配。但是这一结论与 “NOT 找不到左括号匹配” 相矛盾。因此，我们就证明了合法字符串的连续性。

那么，我们是不是可以进行如下操作呢？

Step 1. 把所有配对成功的下标，都放到一个数组中，然后再把这个数组排序。

Step 2. 找到最长的相邻整数构成的列表，输出其长度。

为了方便你理解 Step 2 中 “最长的相邻整数构成的列表”，这里我给你举个例子：

当给定的数组为 A[] = {0,1,3,4,5,6,8,9} 时，最长的相邻整数列表为 [3,4,5,6]，输出长度 4。

那么，基于这样的思路，我们可以写出代码如下（解析在注释里）：

class Solution {
public int longestValidParentheses(String s) {
final int N = s == null ? 0 : s.length();
if (N <= 1) {
return 0;
    }
    List<Integer> pairs = new ArrayList<>();
    Stack<Integer> st = new Stack<>();
for (int i = 0; i < N; i++) {
final char c = s.charAt(i);
if (c == ')') {
if (!st.empty()) {
final int idx = st.pop();
          pairs.add(idx);
          pairs.add(i);
        }
      } else {
        st.push(i);
      }
    }
    Collections.sort(pairs);
int ans = 0;
int preValue = -1;
int rangeStart = 0;
for (int i = 0; i < pairs.size(); i++) {
final int cur = pairs.get(i);
if (i > 0) {
if (cur != preValue + 1) {
          ans = Math.max(ans, i - rangeStart);
          rangeStart = i;
        }
      }
      preValue = cur;
    }
    ans = Math.max(ans, pairs.size() - rangeStart);
return ans;
  }
}

代码：Java/C++/Python

复杂度分析：最差情况下，会有 N 个整数放到数组中排序，所以时间复杂度为 O(NlgN)，空间复杂度为 O(N)。

我们继续从相连性出发，请你思考，这里是否必须要做排序？既然都相连了，我们就把所有配对成功的字符标记为 1，没有配对成功的字符标记为 -INF，如下图所示：

那么，原问题就成功转化为 “求一个数组的最大子数组” 问题。并且，最大子数组和即是原问题的输出。

基于这个思想，我们可以写出代码如下（解析在注释里）：

class Solution {
public int longestValidParentheses(String s) {
final int N = s == null ? 0 : s.length();
if (N <= 1) {
return 0;
    }
int[] pairPos = new int[N];
    Arrays.fill(pairPos, -1);
    Stack<Integer> st = new Stack<>();
for (int i = 0; i < N; i++) {
final char c = s.charAt(i);
if (c == ')') {
if (!st.isEmpty()) {
          pairPos[i] = st.peek();
          pairPos[st.peek()] = i;
          st.pop();
        }
      } else {
        st.push(i);
      }
    }
int tmp_sum = 0;
int max_sum = 0;
for (int i = 0; i < N; i++) {
final int v = (pairPos[i] == -1) ? Integer.MIN_VALUE / 2 : 1;
      tmp_sum = Math.max(tmp_sum, 0) + v;
      max_sum = Math.max(max_sum, tmp_sum);
    }
return max_sum;
  }
}

代码：Java/C++/Python

复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(N)。

然后，我们再看一下这个题目的下一个特点与解法。

特点 3：最长

我们从题目中看到了 “最长” 二字，这不禁让我想起一个总结：

如果题目中出现 “最大”“最小”“最长” 等字眼，那么可以尝试往 DP 的方向思考。

因此，这里我们就尝试往 DP 的方向去想一想，首先还是拿出 “DP 分析 6 步法”。

1. 最后一步

DP 问题的关键是最后一步。对于处理一维的字符串而言，最后一步肯定就是处理字符串的最后一个字符。最后一个字符可以分为两种情况：左括号、右括号。

• 左括号：此时肯定找不到括号与这个字符配对，所以包含最后一个字符的有效子串长长度为 0。
• 右括号：如果最后一个字符为右括号，那么我们再看它前面的那个字符，这个字符也只有 2 种情况（左括号，右括号）。

1） 左括号

情况如下图所示：

此时，最后一个字符可以和它前面的字符配对成功。但是需要注意：包含最后一个括号的合法子串长度可能是 2，也可能比 2 大。因为可能有如下 2 种情况：

情况 1，前面字符串不是有效的合法子串，此时最后一个括号的合法子串长度是 2。如下图所示：

情况 2，前面的字符串也是有效的合法子串。我们需要加上这部分的合法子串的长度。此时最后一个括号的合法子串长度大于 2。如下图所示：

2）右括号

如果最后一个括号之前的字符是右括号，如下图所示：

那么我们只需要跳过前面那一段有效合法子串，看一下 “问号” 位置（与最后一个字符可能匹配的位置 pairPos）是否可以与最后一个字符匹配。

• 如果问号位置（s[pairPos]）是一个右括号，那么最后一个字符肯定匹配失败；
• 如果问号位置（s[pairPos]）是一个左括号，那么就可以配对成功。

在配对成功的情况下，我们还需要加上之前的合法子串的长度。情况如下：

我们可以将这里分情况的思路用思维导图整理如下：

分情况讨论总是很烦，所以这里我给你总结成两条原则：

• 配对失败，那么此字符的合法子串长度为 0；
• 配对成功，还需要加上之前的合法长度。

2. 子问题

我们可以用 f(x) 表示以字符 s[x] 为右端点的，合法子串的长度。

3. 递推关系

有了 “f(x)” 的含义，可以写出递推的伪代码如下（解析在注释里）：

if s[i-1] == '(':
    f(i) = 2 + f(i-2) 
else:
    preValidLen = f(i-1)
    pairPos = i - preLen - 1
if pairPos >= 0 and s[pairPos] == '(':
        f(i) = i + 1 - pairPos
if pairPos - 1 >= 0: 
            f(i) += f(pairPos-1)

4. f(x) 的表达

我们发现，x 只是字符串 s 的下标，那么只需使用一个一维的数组 dp[] 就可以表示 f(x) 了。

5. 初始条件与边界

在计算的时候，f(i) 会依赖 f(i-1) 以及 f(i-2)，还有 f(pairPos-1)。这里提醒我们：

• 由 f(i) 依赖 f(i-1)、f(i-2)，可知初始计算的时候，至少应该先计算出两项的值，也就是计算出 f(0) 和 f(1)；
• 由于我们并不清楚 f(pairPos-1) 具体的值是多少，所以在处理的时候，要注意判断是否越界。

6. 计算顺序

如果我们从左往右遍历字符串，那么计算的时候，需要注意：

• 处理字符串为空，或者长度为 1 的特殊情况；
• 优先计算头两个字符的 f() 函数值；
• 注意 pairPos 的越界的处理。

至此，我们就可以写出动态规划求解的代码了（解析在注释里）：

class Solution {
public int longestValidParentheses(String s) {
final int N = s == null ? 0 : s.length();
if (N <= 1) {
return 0;
    }
int[] dp = new int[N];
int ans = 0;
if (s.charAt(0) == '(' && s.charAt(1) == ')') {
      dp[1] = 2;
      ans = 2;
    }
for (int i = 2; i < N; i++) {
final char c = s.charAt(i);
if (c == ')') {
final char preChar = s.charAt(i - 1);
if (preChar == '(') {
          dp[i] = 2 + dp[i - 2];
        } else {
final int preLen = dp[i - 1];
final int start = i - preLen;
final int pairPos = start - 1;
if (pairPos >= 0 && s.charAt(pairPos) == '(') {
int curLen = i + 1 - pairPos;
if (pairPos - 1 >= 0) {
              curLen += dp[pairPos - 1];
            }
            dp[i] = curLen;
          }
        }
      }
      ans = Math.max(ans, dp[i]);
    }
return ans;
  }
}

代码：Java/C++/Python

复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(N)。

在使用 DP 的过程中，我们发现，可以浓缩成一个原则：

配对成功，就加上之前的合法长度。

那么，基于这个原则我们还有没有其他解法呢？

特点 4：栈的性质

在特点 1 和特点 2 中，都用到了栈来找到每一个字符的匹配字符的位置（如果存在）。下面我们再看一下，当一个合法的字符串利用栈来进行匹配处理的时候，有什么样的性质。

stack = []
for i in range(len(s)):
if s[i] == ')':
if not stack.empty():
            topIdx = stack.pop()
            <topIdx, i>匹配成功
else:
else:
       stack.push(i)

问题 1：弹栈之后的空栈

当我们需要为红框中的右括号 s[i] 进行匹配，并且弹栈之后，栈为空。那么我们可以得到一个结论 1：

此时，整个字符串从开头到当前位置是一个合法有效的字符串。

但是，这个结论 1会遇到下面这种坑。

例 1：给定的字符串是 “)))()”，当我们处理最后一个字符 s[4] 的时候，弹栈之后，栈肯定为空。但是，我们不能认为 [0, 4] 是一个有效的合法子串。

那么，是不是结论 1 不对呢？其实不尽然，只是我们有可能需要重新定义字符串的开头。

问题 2：空栈无法弹

假设，字符串是 s = “))))”。如果按照结论 1 来进行操作，每个位置都会得到空栈，我们可以得到每个位置的最长合法子串，如下图所示：

显然，这样处理是不合适的。那么问题出在哪里呢？

在特点 2 中，我们证明了合法字符串必须满足连续性，那么当我们找到一个右括号，但是找不到任何左括号与之配对的时候，就可以扔掉左边的字符了。

这也就意味着，在找到一个字符 s[i]，找不到匹配的时候，需要切掉 [0,i] 这部分子串。

当然，为了处理方便，我们不会真正去切这个子串，而是重新定义一个 start 变量来表示新的字符串的起始位置。

在切掉 [0, i] 这部分子串的时候，就可以有如下操作：

当 s[i] 为右括号，栈为空的时候，设置新的字符串的起始点 start = i + 1。

打上这个补丁之后，字符串 s = “))))” 就可以正确处理了。到此时，我们发现，并不是结论 1 不对，而是结论 1 中的 “开头 start” 在遇到空栈无法弹的时候，需要重新定义。

问题 3：弹栈后非空

如果弹栈之后，栈非空，那么必然是遇到了 s = “((()()(）” 这种字符串。当我们处理最后一个字符（会将 6 弹栈），如下图所示：

但是，弹栈之后，栈顶元素就变成了 1。我们发现 (1, 7] 这段区间都是一个有效的合法区间。因此，弹栈之后，栈非空的情况：区间（存留的栈顶元素，i] 是一个合法的子串。

处理好问题 1、问题 2、问题 3 之后，我们就可以写出如下代码了（解析在注释里）：

class Solution {
public int longestValidParentheses(String s) {
final int N = s == null ? 0 : s.length();
if (N <= 1) {
return 0;
    }
    Stack<Integer> st = new Stack<>();
int ans = 0;
int start = 0;
for (int i = 0; i < N; i++) {
final char c = s.charAt(i);
if (c == ')') {
if (st.isEmpty()) {
          start = i + 1;
        } else {
          st.pop();
final int base =
              st.isEmpty() ? start : st.peek() + 1;
          ans = Math.max(ans, i - base + 1);
        }
      } else { 
        st.push(i);
      }
    } 
return ans;
  }
}

代码：Java/C++/Python

复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(N)。

前面我们介绍的算法最优情况下，时间复杂度都是 O(N)，但是空间复杂度也都为 O(N)。有没有可能优化一下空间复杂度呢？

特点 5：合法字符串的性质

如果优化空间复杂度，我们需要再挖掘一下合法子串的性质。对于任意一个合法子串，都必然满足以下两个性质。

• 合法性质 1：对于任意一个合法子串，当我们从左往右遍历这个子串的时候，左括号的数目永远 >= 右括号的数目。
• 合法性质 2：对于任意一个合法子串，当我们从右往左遍历这个子串的时候，右括号的数目永远 >= 左括号的数目。

那么，我们是否可以反推呢？

1） 利用合法性质 1，我们从左往右遍历，找到一个最长的区间，使其总是满足左括号的数目 >= 右括号的数目。那么当左括号数目 == 右括号数目，此时就可以得到一个最长的合法子串，我们记为 maxEquLength1。

2）利用合法性质 2，我们从右往左遍历，找到一个最长的区间，使其总是满足右括号的数目 >= 左括号的数目。那么当左括号数目 == 右括号数目，此时就可以得到一个最长的合法子串，我们记为 maxEquLength2。

最后，再取这两者的最大值：max(maxEquLength1, maxEquLength2)。

那么，有没有可能只从左向右遍历一次呢？答案是不行！

原因是：如果只利用合法性质 1 从左向右遍历，那么无法处理字符串 s = “(()”；如果只利用合法性质 2 从右向左遍历，那么无法处理字符串 s = “())”。

结合以上分析，我们可以写出如下代码（解析在注释里）：

class Solution {
public int longestValidParentheses(String s) {
final int N = s == null ? 0 : s.length();
if (N <= 1) {
return 0;
    }
int leftBraceNumber = 0;
int rightBraceNumber = 0;
int maxEquLength1 = 0;
for (int i = 0; i < N; i++) {
final char c = s.charAt(i);
      leftBraceNumber += c == '(' ? 1 : 0;
      rightBraceNumber += c == ')' ? 1 : 0;
if (rightBraceNumber > leftBraceNumber) {
        leftBraceNumber = 0;
        rightBraceNumber = 0;
      }
if (leftBraceNumber == rightBraceNumber) {
        maxEquLength1 =
          Math.max(maxEquLength1,
                   leftBraceNumber + rightBraceNumber);
      }
    } 
int maxEquLength2 = 0;
    leftBraceNumber = 0;
    rightBraceNumber = 0;
for (int i = N - 1; i >= 0; i--) {
final char c = s.charAt(i);
      leftBraceNumber += c == '(' ? 1 : 0;
      rightBraceNumber += c == ')' ? 1 : 0;
if (leftBraceNumber > rightBraceNumber) {
        leftBraceNumber = 0;
        rightBraceNumber = 0;
      }
if (leftBraceNumber == rightBraceNumber) {
        maxEquLength2 =
          Math.max(maxEquLength2,
                   leftBraceNumber + rightBraceNumber);
      }
    } 
return Math.max(maxEquLength1, maxEquLength2);
  }
}

代码：Java/C++/Python

复杂度分析：时间复杂度为 O(N)，空间复杂度为 O(1)。

在这里，我们抓住了合法字符串的性质 1 和性质 2，然后利用贪心算法在 O(1) 空间内解决了这个题目。在做题的时候，如果挖掘出题目的更多信息，再匹配到合适的算法，就能够帮助我们巧妙地破题。

总结

在本讲，我们通过一个括号匹配的题目，深入挖掘了题目的特点，然后再使用上各种算法与数据结构，得到了各种巧妙的解法。我将本讲的内容整理成了思维导图，帮助你总结思路：

思考题

最后，我还给你留了一个思考题。

思考题：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1

输入：n = 3

输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

代码：Java/C++/Python

你可以自己尝试求解这道题目，把答案写在留言区，我们一起讨论。关于这道括号的题目就介绍到这里。接下来，下一讲介绍 “21 | 安排会议室：如何利用多种方法安排会议室？”，让我们继续前进。