括号Leetcode解决方案的最大嵌套深度


难度级别 易得奖学金
经常问 彭博

问题陈述

在这个问题上,我们得到一个有效的括号 绳子 (vps)具有一些数字,一些运算符(例如+,-,*)和一些括号(例如'(',')')。
有效的括号字符串(vps)为:

  1.  “,”
  2. “ d”,其中d是任意数字
  3. “(A)”,如果A是有效的括号字符串
  4. 如果*是任意运算符,并且A和B是有效的括号字符串,则为“ A * B”。

我们的目的是找到给定字符串中括号的最大深度。
e.g. “(1+(2*3)+((8)/4))+1”
我们可以看到,数字8在最大括号内,括号的深度是3。我们将输出3。

括号Leetcode解决方案的最大嵌套深度
再来看一个例子
e.g. “1+(2*3)/(2-1)”
vps 2 * 3或另一个vps 2-1都在最大括号内,即1。

使用案列

s = "(1+(2*3)+((8)/4))+1"
3

说明:

数字8在字符串的3个嵌套括号内。

s = "(1)+((2))+(((3)))"
3

途径

我们假设该字符串是一个vps,我们只需要找出括号的最大深度即可。 因此,我们可以只关注括号,而忽略其他字符(数字和运算符)。

仅当开始新的嵌套括号时,括号的深度才会增加。 也就是说,起始括号'('表示括号的深度增加1。当括号关闭时,深度减小1。即')'表示深度减小1。

在我们的方法中,我们将只使用当前的深度变量(let k)和最大深度变量(let ans),两者都被初始化为0(深度0表示我们最初不在所有括号内)。 并开始从左到右遍历输入字符串。 根据我们讨论的技巧,每当遇到一个'('符号时,我们将当前深度k增加1,而每当遇到一个')'符号时,我们将当前深度k减小1。
每次我们都会检查当前深度是否大于最大深度。 如果是,则将当前深度分配给最大深度变量。
最终在遍历之后,我们的ans变量存储了最大深度,因此我们将输出它。

实施

括号Leetcode解决方案的最大嵌套深度的C ++程序

#include <iostream>
using namespace std;

int maxDepth(string s) 
{
    int ans=0,k=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='(')k++;
        else if(s[i]==')')k--;
        ans=ans>k?ans:k;
    }
    return ans;
}
int main()
{
    cout<<maxDepth("(1)+((2))+(((3)))");
}
3

Java程序,用于使括号Leetcode解决方案具有最大嵌套深度

import java.util.*;
import java.lang.*;

class Solution
{  
    public static int maxDepth(String s) 
    {
        int ans=0,k=0;
        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)=='(')k++;
            else if(s.charAt(i)==')')k--;
            ans=Math.max(ans,k);
        }
        return ans;
    }
    
    public static void main(String args[])
    {
        System.out.println(maxDepth("(1)+((2))+(((3)))"));
    }
}
3

括号Leetcode解决方案的最大嵌套深度的复杂度分析

时间复杂度

上): 我们正在从左到右遍历给定的表达式。 因此它是O(n),其中n是给定字符串的长度。

空间复杂度 

O(1): 我们没有使用常量多余的空间。 因此,空间复杂度为O(1)。