题解 | 括号匹配深度

Ps：含有两版代码

一。思路：

很显然，这是一个括号匹配问题。我们可以这样理解题意：

1.一旦有 '(' ，就必然有 ')' 。

2.可以只关注括号。

3.输出只有一个，就是最大值。

由此，我们给出示例：

1.(x) 型：（） -> out：1

2.(xy) 型：(()(())) -> out: 3

不难发现：

1.无论怎样，一个x（或 y）的值只取决于其所具有的 '(' 或 ')' 的个数。

2. out = max（x_i）。

所以：

我们只需要去找到每个x所具有的 '(' 或 ')' 的个数就行了！

观察发现：

将 '(' 理解为进入x，则 ')' 可以理解为出x，我们要的x的值就必然在进出的转折点，所以，我们可以将 ')' 作为一个信号。

结论：

用cnt 记录x的值，当 '(' 出现时就 +1 操作，当 ')' 出现时就 -1 操作，同时用 max 记录下x的值。

二。代码：

//第一版 （记录了每一个x的值，便于理解？）

#include<iostream>
#include<string>
using namespace std;

int cnt[100];

int main() {
    string t, s = " ";
    cin >> t;
    s += t;
    int len = s.length();

    for (int i = 1; i < len; i++) {
        if (s[i] == '(') cnt[i] = cnt[i - 1] + 1;
        else if (s[i] == ')') cnt[i] = cnt[i - 1] - 1;
        else cnt[i] = cnt[i - 1];
    }
    int max = -1;
    for (int i = 1; i < len; i++) {
        max = max > cnt[i] ? max : cnt[i];
    }

    cout << max << endl;


    return 0;
}

//第二版，优化（ps：hi hi)

#include<cstdio>
char ch;
int depth, max;

int main() {
    while ((ch = getchar()) && ch != EOF) {
        if (ch == '(') depth++;
        else if (ch == ')') max = max > depth-- ? max : depth+1;
    }
    printf("%d\n", max);

    return 0;
}

三。作者有话说：

其实一开始想用递归的，但是发现条件难找，就放弃了。另外，我写的真的很认真了，希望能帮到你！