每日一题:LeetCode:1614.括号的最大嵌套深度

浏览次数 : 次 2022-01-07

博文字数统计 : 1k字 | 阅读所需时长 : 4分

× 文章目录

1. 2022-01-07：LeetCode：1614.括号的最大嵌套深度
1. 1.1. 1. 题目描述
2. 1.2. 2. 方法：字符串模拟

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

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字符串的长度
- 时间复杂度：$O(n)$，遍历了整个字符串
- 空间复杂度：$O(1)$，无栈模拟
- 空间复杂度：$O(n)$，有栈模拟

题解：无栈模拟

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;
}

本文作者： Chthollists
发布时间： 2022-01-07 14:48:56
最后更新： 2022-01-21 23:09:05
本文标题： 每日一题:LeetCode:1614.括号的最大嵌套深度
本文链接： https://chthollists.github.io/post/a2d58b9c.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！