• 每日一题：LeetCode：1614.括号的最大嵌套深度
  • 时间：2022-01-07
  • 力扣难度：Easy
  • 个人难度：Easy
  • 数据结构：字符串、栈
  • 算法：模拟

谢拉.jpg

2022-01-07：LeetCode：1614.括号的最大嵌套深度

1. 题目描述

• 题目：原题链接

  • 如果字符串满足以下条件之一，则可以称之为有效括号字符串(valid parentheses string，可以简写为 VPS)

    • 字符串是一个空字符串 ""，或者是一个不为 ( 或 ) 的单字符
    • 字符串可以写为 AB，表示A与B字符串连接，其中A和B都是 有效括号字符串
    • 字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。

  • 类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：

    • depth("") = 0
    • depth(C) = 0，其中C是单个字符的字符串，且该字符不是 ( 或 )
    • depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
    • depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串

  • 给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。

• 输入输出规范

  • 输入：字符串s，题目保证字符串是VPS
  • 输出：VPS的最大嵌套深度

• 输入输出示例

  • 输入：s = "(1+(2*3)+((8)/4))+1"
  • 输出：3

2. 方法：字符串模拟

• 思路

  • 本题因为题目指定了输入的字符串为有效括号字符串VPS，所以无需考虑左括号和右括号数目不一致的情况
  • 括号匹配类型的问题以及表达式计算等问题，一般都是根据栈的思想来模拟，由于本题最终只需要返回最大嵌套深度，即忽略非括号内容后，连续的左括号的最大个数，所以无需真的使用栈来模拟，只需要根据栈的思想模拟即可
  • 模拟的思路：维护两个变量，分别为当前深度和最大深度，对VPS字符串进行遍历，当前深度遇到左括号+1，遇到右括号-1，最大深度取自身和当前深度中的最大值即可
  • 如果最终结果不是返回最大嵌套深度，而是返回计算结果、表达式的某一部分，此时需要使用栈结构来模拟

• 复杂度分析：n是s字符串的长度

  • 时间复杂度：，遍历了整个字符串
  • 空间复杂度：，无栈模拟
  • 空间复杂度：，有栈模拟

• 题解：无栈模拟

  public int maxDepth(String s) {
      if(s == null || s.length() == 0) return 0;
      int curDepth = 0; // 记录当前深度
      int maxDepth = 0; // 记录最大深度
      for (int i = 0; i < s.length(); i++) {
          if(s.charAt(i)  == '(') {
              curDepth++;
              maxDepth = Math.max(maxDepth,curDepth);
          }else if(s.charAt(i) == ')') {
              curDepth--;
          }
      }
      return maxDepth;
  }
  

• 题解：有栈模拟：

  public int maxDepth(String s) {
      Deque<Character> stack = new LinkedList<>();
      int maxDepth = 0;
      for (int i = 0; i < s.length(); i++) {
          // 遇到左括号入栈
          if (s.charAt(i) == '(') {
              stack.add(s.charAt(i));
              maxDepth = Math.max(maxDepth, stack.size());
              // 遇到右括号则栈顶的左括号出栈
          } else if (s.charAt(i) == ')') {
              stack.removeLast();
          }
      }
      return maxDepth;
  }
  

• 思考与优化：输入不是VPS的情况

  • 思考：

    • 输入不是VPS时，即左右括号数目、顺序不匹配
    • 此时可以通过判断当前左右括号的深度来判断是否为VPS
    • 非VPS对应遍历过程中当前左括号深度为负，或当前右括号深度为正，以及遍历结束后的左右括号当前深度不为零的情况

  • 题解：

    public int maxDepth(String s) {
        if(s == null || s.length() == 0) return 0;
        int curLeft = 0; // 记录左括号
        int curRight = 0; // 记录右括号
        int maxDepth = 0; // 记录最大深度
        for (int i = 0; i < s.length(); i++) {
            if(curLeft < 0 || curRight > 0) return 0;
            if(s.charAt(i)  == '(') {
                curLeft++;
                curRight--;
                maxDepth = Math.max(maxDepth,curLeft);
            }else if(s.charAt(i) == ')') {
                curLeft--;
                curRight++;
            }
        }
        boolean isVps = curLeft == 0 && curRight == 0;
        return isVps ? maxDepth : 0;
    }
    

最后

新人LeetCoder，发布的题解有些会参考其他大佬的思路(参考资料的链接会放在最下面)，欢迎大家关注我 ~ ~ ~
如果本文有所帮助的话，希望大家可以给个三连「点赞」&「收藏」&「关注」 ~ ~ ~
也希望大家有空的时候光临我的「个人博客」。