【栈结构应用】牛客14496题：括号匹配深度问题的最优解法全解析

问题描述

给定一个合法的括号序列，求其最大嵌套深度。例如："(())()"的最大深度为2。

算法思路

使用栈数据结构来跟踪括号的嵌套深度：

1. 初始化当前深度和最大深度为0

2. 遍历字符串：

• 遇到'('时深度+1，更新最大深度

• 遇到')'时深度-1

C++代码实现

#include <iostream>
#include <string>
#include <algorithm>
using namespACe std;

int maxDepth(string s) {
    int current = 0;    // 当前深度
    int max_d = 0;      // 最大深度
    
    for(char c : s) {
        if(c == '(') {
            current++;          // 遇到左括号，深度+1
            max_d = max(max_d, current);  // 更新最大深度
        }
        else if(c == ')') {
            current--;          // 遇到右括号，深度-1
        }
    }
    
    return max_d;
}

int main() {
    string input;
    cin >> input;
    cout << maxDepth(input) << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(n)，只需遍历字符串一次

• 空间复杂度：O(1)，仅使用常数空间

关键点解析

1. 字符串必须合法（题目已保证）

2. 不需要真正使用栈，只需计数即可

3. 每次遇到'('都要检查是否需要更新最大深度

边界情况

1. 空字符串返回0

2. 单对括号"()"返回1

3. 深度最大的情况如"(((...)))"

实际应用

这种算法在编译器设计、JSON/XML解析、代码格式化等场景都有重要应用。