牛客14496题解：括号最大深度问题（栈思想与代码优化）

一、题目解读

牛客14496题要求计算给定括号字符串中的最大深度。例如，对于字符串 "(()())"，最大深度为2。题目考察对括号嵌套结构的理解，以及如何通过编程找到最深嵌套层次。

二、解题思路

采用栈思想的简化版本：无需显式使用栈数据结构，而是通过计数器模拟栈行为。核心逻辑是：

1. 遍历字符串，遇到左括号深度+1，右括号深度-1。

2. 实时更新当前深度与历史最大深度。

此思路将嵌套深度转化为“括号平衡计数”，避免复杂数据结构，提升效率。

三、解题步骤

1. 初始化变量：当前深度 current 与最大深度 max_d 均设为0。

2. 遍历字符串：

○ 若遇 ('，current++ 并更新 max_d（若 current 更大）。

○ 若遇 ')'，current--（模拟栈弹出）。

3. 返回结果：遍历结束后，max_d 即为所求最大深度。

四、代码与注释

#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 == '(') {  // 遇左括号，深度+1
            current++;
            max_d = max(max_d, current);  // 更新最大深度
        }
        else if(c == ')') {  // 遇右括号，深度-1
            current--;
        }
    }
    
    return max_d;
}

int main() {
    string input;
    cin >> input;      // 输入字符串
    cout << maxDepth(input) << endl;  // 输出结果
    return 0;
}

注释：代码通过单次遍历实现O(n)时间复杂度，利用 current 实时记录深度，max_d 保存历史最大值，无需额外空间，简洁高效。

五、总结

本解法巧妙将括号匹配问题转化为计数问题，无需栈操作，降低空间开销。通过“边遍历边更新”的策略，实现线性时间复杂度。此思路适用于同类括号嵌套深度计算场景，对编程面试与算法练习具有参考价值。