题目链接

HIGH13 括号匹配深度

题目描述

一个合法的括号匹配序列有以下定义:

  1. 空串""是一个合法的括号匹配序列
  2. 如果"X"和"Y"都是合法的括号匹配序列,"XY"也是一个合法的括号匹配序列
  3. 如果"X"是一个合法的括号匹配序列,那么"(X)"也是一个合法的括号匹配序列
  4. 每个合法的括号序列都可以由以上规则生成。

对于一个合法的括号序列我们又有以下定义它的深度:

  1. 空串""的深度是0
  2. 如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度为max(x,y)
  3. 如果"X"的深度是x,那么字符串"(X)"的深度是x+1

例如: "()()()"的深度是1,"((()))"的深度是3。牛牛现在给你一个合法的括号序列,需要你计算出其深度。

输入描述: 输入包括一个合法的括号序列s,s长度length(2 ≤ length ≤ 50),序列中只包含'('和')'。

输出描述: 输出一个正整数,即这个序列的深度。

解题思路

这道题要求我们计算一个合法括号序列的深度。我们可以通过一次遍历来解决这个问题。

我们维护一个变量 current_depth 来表示当前遇到的未匹配的左括号数量，同时用另一个变量 max_depth 来记录遍历过程中的最大深度。

  • 当我们遇到一个左括号 ( 时，说明我们进入了更深一层嵌套，current_depth 加 1。此时，我们需要更新 max_depth 为 max(max_depth, current_depth)。
  • 当我们遇到一个右括号 ) 时，说明我们结束了当前层的嵌套，current_depth 减 1。

遍历结束后，max_depth 的值就是整个括号序列的深度。

例如，对于 s = "(())"：

  1. 遇到第一个 (：current_depth 变为 1。max_depth 更新为 1。
  2. 遇到第二个 (：current_depth 变为 2。max_depth 更新为 2。
  3. 遇到第一个 )：current_depth 变为 1。
  4. 遇到第二个 )：current_depth 变为 0。

整个过程中的最大深度为 2，所以结果是 2。

代码

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

using namespace std;

int main() {
    string s;
    cin >> s;
    
    int max_depth = 0;
    int current_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 maxDepth = 0;
        int currentDepth = 0;
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                currentDepth++;
                maxDepth = Math.max(maxDepth, currentDepth);
            } else if (c == ')') {
                currentDepth--;
            }
        }
        
        System.out.println(maxDepth);
    }
}

s = input()

max_depth = 0
current_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)

算法及复杂度

  • 算法：计数法 (模拟栈)
  • 时间复杂度：，其中 是字符串的长度。我们只需要遍历一次字符串。
  • 空间复杂度：，我们只需要常数个变量来存储深度。