ความลึกของการซ้อนสูงสุดของวงเล็บ Leetcode Solution


ระดับความยาก สะดวกสบาย
ถามบ่อยใน บลูมเบิร์ก
เชือก

คำชี้แจงปัญหา

ในปัญหานี้เราจะได้รับวงเล็บที่ถูกต้อง เชือก (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 Solution
มาดูอีกหนึ่งตัวอย่าง
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. ie ')' หมายถึงความลึกจะลดลง 1

ในแนวทางของเราเราจะใช้ตัวแปรความลึกปัจจุบัน (ให้ k) และตัวแปรความลึกสูงสุด (ให้ 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 Solution

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 Solution

ความซับซ้อนของเวลา

บน): เรากำลังสำรวจนิพจน์ที่กำหนดจากซ้ายไปขวา ดังนั้นจึงเป็น O (n) โดยที่ n คือความยาวของสตริงที่กำหนด

ความซับซ้อนของอวกาศ 

O (1): เราไม่ได้ใช้ช่องว่างพิเศษคงที่ ดังนั้นความซับซ้อนของพื้นที่จึงเป็น O (1)