Максимальная глубина вложения круглых скобок Решение Leetcode


Сложный уровень Легко
Часто спрашивают в Bloomberg
строка

Постановка задачи

В этой задаче нам даны правильные круглые скобки строка (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 находится внутри трех вложенных скобок в строке.

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

Подход

Нам дано, что строка является vps, и нам просто нужно узнать максимальную глубину скобок. Итак, мы можем просто сосредоточиться на круглых скобках и игнорировать другие символы (числа и операторы).

Глубина скобок увеличивается только тогда, когда начинается новая вложенная скобка. т.е. начальные скобки '(' означают, что глубина скобок увеличивается на 1. А когда скобки закрываются, глубина уменьшается на 1. т.е. ')' означает, что глубина уменьшается на 1.

В нашем подходе мы просто будем использовать текущую переменную глубины (let k) и переменную максимальной глубины (let ans). Обе инициализируются значением 0 (глубина 0 означает, что изначально у нас нет всех круглых скобок). И начните обход входной строки слева направо. Согласно описанному нами трюку, всякий раз, когда мы встречаем знак '(', мы увеличиваем текущую глубину k на 1, а всякий раз, когда мы встречаем знак ')', мы уменьшаем текущую глубину k на 1.
Каждый раз мы будем проверять, превышает ли текущая глубина максимальную глубину. Если да, то мы присвоим текущую глубину переменной максимальной глубины.
Наконец, после обхода наша переменная ans сохранила максимальную глубину, поэтому мы выведем ее.

Реализация

Программа C ++ для максимальной глубины вложения круглых скобок Решение Leetcode

#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 - длина данной строки.

Космическая сложность 

О (1): Мы не использовали постоянные лишние пробелы. Таким образом, сложность пространства O (1).