题目链接

括号匹配深度

题目描述

给定一个合法的括号匹配序列 ，你需要计算出它的深度。深度的定义如下：

  1. 空串 "" 的深度是 。
  2. 如果字符串 X 和 Y 都是合法的括号匹配序列，它们的深度分别为 和 ，那么字符串 XY 的深度为 。
  3. 如果 X 的深度是 ，那么字符串 (X) 的深度是 。

解题思路

本题要求计算一个合法括号序列的最大嵌套深度。这个问题可以通过一次简单的线性扫描来解决。

我们可以维护一个计数器来实时追踪当前遍历到的位置的括号嵌套深度。具体算法如下：

  1. 初始化两个整数变量：

    • ：用于记录当前的嵌套深度，初始为 。
    • ：用于记录整个遍历过程中出现过的最大嵌套深度，初始为 。

  2. 从左到右遍历输入的括号序列 中的每一个字符：

    • 如果当前字符是左括号 '('：
      • 说明我们进入了更深一层嵌套，因此将 加 。
      • 更新 ，使其始终保持为已遍历部分出现过的最大深度，即 。
    • 如果当前字符是右括号 ')'：
      • 说明我们退出了当前这一层的嵌套，因此将 减 。

  3. 遍历结束后， 中存储的值就是整个括号序列的最大深度。

由于题目保证输入的序列是合法的，我们无需担心 会变为负数，或者遍历结束后不为 的情况。

代码

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    string s;
    cin >> s;
    
    int current_depth = 0;
    int max_depth = 0;
    
    for (char c : s) {
        if (c == '(') {
            current_depth++;
            max_depth = max(max_depth, current_depth);
        } else if (c == ')') {
            current_depth--;
        }
    }
    
    cout << max_depth << endl;
    
    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        int current_depth = 0;
        int max_depth = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                current_depth++;
                max_depth = Math.max(max_depth, current_depth);
            } else if (c == ')') {
                current_depth--;
            }
        }
        
        System.out.println(max_depth);
    }
}

def main():
    s = input()
    
    current_depth = 0
    max_depth = 0
    
    for char in s:
        if char == '(':
            current_depth += 1
            max_depth = max(max_depth, current_depth)
        elif char == ')':
            current_depth -= 1
            
    print(max_depth)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：线性扫描/遍历

  • 时间复杂度：，其中 是输入括号序列的长度。我们只需要对字符串进行一次完整的遍历。

  • 空间复杂度：，用于存储输入的字符串 。算法本身只需要常数级别的额外空间。