# 資訊

:::info
- Question: 1614. Maximum Nesting Depth of the Parentheses
- From: Leetcode Daily Challenge 2024.04.04
- Difficulty: Easy
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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

1. It is an empty string `""`, or a single character not equal to `"("` or `")"`,
2. It can be written as `AB` (`A` concatenated with `B`), where `A` and `B` are VPS's, or
3. 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:

1. `depth("") = 0`
2. `depth(C) = 0`, where `C` is a string with a single character not equal to `"("` or `")"`.
3. `depth(A + B) = max(depth(A), depth(B))`, where `A` and `B` are VPS's.
4. `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:
:::success
* Input: s = "(1+(2*3)+((8)/4))+1"
* Output: 3
* Explnation: Digit 8 is inside of 3 nested parentheses in the string.
:::

> Example 2:
:::success
* Input: s = "(1)+((2))+(((3)))"
* Output: 3
:::

> Constraints:
:::success
* 1 <= `s.length` <= 100
* s consists of digits `0`-`9` and characters `'+'`, `'-'`, `'*'`, `'/'`, `'('`, and `')'`.
* It is guaranteed that parentheses expression `s` is a VPS.
:::

---

# 解法

## 概念

這題雖然說 stack，但其實不用真的開一個 stack 去紀錄，因為只要知道最深的深度是多少，其實重心放在最深的左括號就好，因此當我遇到一個左括號，我就會將目前深度 +1，反之當我遇到右括號，深度就會 -1，這樣去看左括號最深深度在哪裡就可以知道答案了

唯一要注意的就是深度這件事情他並沒有要求括號不能算，也就是說 `((()))` 和 `(((5)))` 對這題來說都是 3，因此才說重心放在左括號上即可，其他括號以外的符號不需考慮

## 程式碼

class Solution:
    def maxDepth(self, s: str) -> int:
        ans = 0
        count = 0
        for e in s:
            if e == '(':
                count += 1
                ans = max( ans, count )
            elif e == ')':
                count -= 1
        return ans

---

# 複雜度

## 時間複雜度

這邊我 traverse 完整一次 `s`，所以是 $O(n)$


## 空間複雜度

空間部分就是紀錄深度，所以是 $O(1)$