LeetCode（Stack)1614. Maximum Nesting Depth of the Parentheses

╰半橙微兮° 2023-09-25 22:49 27阅读 0赞

# 1.问题 #

A string is a valid parentheses string (denoted VPS) if it meets one of the following:

It is an empty string “”, or a single character not equal to “(” or “)”,  
It can be written as AB (A concatenated with B), where A and B are VPS’s, or  
It can be written as (A), where A is a VPS.  
We can similarly define the nesting depth depth(S) of any VPS S as follows:

depth(“”) = 0  
depth© = 0, where C is a string with a single character not equal to “(” or “)”.  
depth(A + B) = max(depth(A), depth(B)), where A and B are VPS’s.  
depth(“(” + A + “)”) = 1 + depth(A), where A is a VPS.  
For example, “”, “()()”, and “()(()())” are VPS’s (with nesting depths 0, 1, and 2), and “)(” and “(()” are not VPS’s.

Given a VPS represented as string s, return the nesting depth of s.

Example 1:

> Input: s = “(1+(2\*3)+((8)/4))+1”  
> Output: 3  
> Explanation: Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

> Input: s = “(1)+((2))+(((3)))”  
> Output: 3

Constraints:

*  1 <= s.length <= 100
 *  s consists of digits 0-9 and characters ‘+’, ‘-’, ‘\*’, ‘/’, ‘(’, and ‘)’.
 *  It is guaranteed that parentheses expression s is a VPS.

# 2. 解题思路 #

## 方法1： ##

> 1.首先，初始化深度为0，当前深度为0。  
> 2.然后，遍历字符串中的每个字符。如果字符为左括号，当前深度加1，同时更新深度的最大值；如果字符为右括号，当前深度减1。  
> 3.最后，返回深度的最大值。

## 方法2： ##

> 遍历字符串，遇到左括号就入栈，遇到右括号就出栈，每次出栈都不需要考虑具体括号的匹配，每次入栈左括号时更新当前嵌套深度（即栈大小），取最大值即为最大嵌套深度。

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int maxDepth(String s) {
        
            int depth = 0; // 初始化深度为0
            int currentDepth = 0; // 初始化当前深度为0
    
            for (char c : s.toCharArray()) {
         // 遍历字符串中的每个字符
                if (c == '(') {
         // 如果字符为左括号
                    currentDepth++; // 当前深度加1
                    depth = Math.max(depth, currentDepth); // 更新深度的最大值
                } else if (c == ')') {
         // 如果字符为右括号
                    currentDepth--; // 当前深度减1
                }
            }
    
            return depth; // 返回深度的最大值
        }
    }

## 代码2： ##

class Solution {
        
        public int maxDepth(String s) {
        
            // 初始化计数器和栈
            int depth = 0;
            Stack<Character> stack = new Stack<>();
            
            // 遍历字符串中的每个字符
            for (char c : s.toCharArray()) {
        
                if (c == '(') {
         // 如果字符是左括号，将其推入栈中
                    stack.push(c);
                    // 更新当前嵌套深度（栈的大小）
                    depth = Math.max(depth, stack.size());
                } else if (c == ')') {
         // 如果字符是右括号，弹出栈顶元素
                    stack.pop();
                }
            }
            
            return depth; // 返回嵌套深度
        }
    }