题目描述与示例
题目
现有一字符串 仅由 '(', ')', '{', '}', '[', ']' 一共六种括号组成。若字符串满足以下条件之一，则为无效字符串
- 任意类型的左右括号数量不相等
- 存在未按正确顺序（先左后右）合的括号，
输出括号的最大嵌套深度，若字符串无效则输出 0。0 <= 字符串长度 <= 100000
输入
一个只包括 '(', ')', '{', '}', '[', ']' 以一共6种字符的字符串。
输出
一个整数，表示最大的括号深度。若字符串无效，则输出 0
示例一
输入
[]
输出
1
说明
该字符串有效，且最大嵌套深度为 1
示例二
输入
([]{()})
输出
3
说明
该字符串有效，且最大嵌套深度为 3
示例三
输入
(]
输出
0
说明
该字符串无效
示例四
输入
([)]
输出
0
说明
该字符串无效
示例五
输入
)(
输出
0
说明
该字符串无效
解题思路
注意，本题和LC20.有效的括号几乎完全一致。唯一的区别在于，本题除了需要判断括号是否有效，还需要判断括号嵌套的深度。
关于字符串是否有效的判断，我们在LC20.有效的括号中已经详细讲解了。基本思路就是：
- 遇到左括号：入栈
- 遇到右括号：弹出栈顶左括号并与当前右括号判断是否配对
一旦出现异常，我们所设置的isError变量就修改为True。
这里主要讨论如何计算括号深度depth的问题。很容易发现：
- 一旦遇到一个左括号，
depth就会+1 - 一旦遇到一个右括号，
depth就会-1。
所以我们只需要把这个逻辑加入原先的代码中即可。每一次depth增大，我们都更新一次答案ans即可。
代码
Python
# 题目：2023Q1A-括号检查
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：栈
# 代码看不懂的地方，请直接在群上提问
s = input()
# 初始化用于判断异常的变量isError，初始化为False表示没有异常
isError = False
# 初始化答案变量ans和记录当前深度的变量cur_depth
ans, cur_depth = 0, 0
# 构建三种括号的两两配对关系
pairs = [('(', ')'), ('{', '}'), ('[', ']')]
# 若字符串长度为奇数，必定无法配对，isError设置为True
if len(s) % 2 == 1:
isError = True
else:
# 使用列表list初始化一个空栈
stack = list()
# 一次遍历字符串s中的每一个字符ch
for ch in s:
# 若ch为某种左括号
if ch == '(' or ch == '{' or ch == '[':
# 则将ch加入栈顶，同时括号深度+1，更新最大括号深度
stack.append(ch)
cur_depth += 1
ans = max(ans, cur_depth)
# 若ch为某种右括号
else:
# 若此时栈为空
if len(stack) == 0:
# 该右括号无法与左括号配对，出现异常，isError设置为True，同时退出循环
isError = True
break
# 若栈不为空，则弹出栈顶字符，同时括号深度-1
ch_stack_top = stack.pop()
cur_depth -= 1
# 若栈顶左括号字符ch_stack_top和当前右括号字符ch不配对，
# 出现异常，isError设置为True，同时退出循环
if (ch_stack_top, ch) not in pairs:
isError = True
break
# 经过一次遍历后，若仍存在元素，说明存在括号未配对，出现异常，isError设置为True
if len(stack) > 0:
isError = True
# 如果isError标志为True，说明前面某一步出现异常，输出0，否则输出最大深度ans
print(0 if isError else ans)
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
// 初始化用于判断异常的变量isError，初始化为False表示没有异常
boolean isError = false;
// 初始化答案变量ans和记录当前深度的变量cur_depth
int ans = 0;
int cur_depth = 0;
// 构建三种括号的两两配对关系
List<Character[]> pairs = new ArrayList<>();
pairs.add(new Character[]{'(', ')'});
pairs.add(new Character[]{'{', '}'});
pairs.add(new Character[]{'[', ']'});
// 若字符串长度为奇数，必定无法配对，isError设置为True
if (s.length() % 2 == 1) {
isError = true;
} else {
// 使用列表list初始化一个空栈
List<Character> stack = new ArrayList<>();
// 一次遍历字符串s中的每一个字符ch
for (char ch : s.toCharArray()) {
// 若ch为某种左括号
if (ch == '(' || ch == '{' || ch == '[') {
// 则将ch加入栈顶，同时括号深度+1，更新最大括号深度
stack.add(ch);
cur_depth++;
ans = Math.max(ans, cur_depth);
} else {
// 若此时栈为空
if (stack.isEmpty()) {
// 该右括号无法与左括号配对，出现异常，isError设置为True，同时退出循环
isError = true;
break;
}
// 若栈不为空，则弹出栈顶字符，同时括号深度-1
char ch_stack_top = stack.remove(stack.size() - 1);
cur_depth--;
// 若栈顶左括号字符ch_stack_top和当前右括号字符ch不配对，
// 出现异常，isError设置为True，同时退出循环
boolean isPair = false;
for (Character[] pair : pairs) {
if (pair[0] == ch_stack_top && pair[1] == ch) {
isPair = true;
break;
}
}
if (!isPair) {
isError = true;
break;
}
}
}
// 经过一次遍历后，若仍存在元素，说明存在括号未配对，出现异常，isError设置为True
if (!stack.isEmpty()) {
isError = true;
}
}
// 如果isError标志为True，说明前面某一步出现异常，输出0，否则输出最大深度ans
System.out.println(isError ? 0 : ans);
}
}
C++
#include <iostream>
#include <vector>
using namespace std;
int main() {
string s;
getline(cin, s);
// 初始化用于判断异常的变量isError，初始化为False表示没有异常
bool isError = false;
// 初始化答案变量ans和记录当前深度的变量cur_depth
int ans = 0;
int cur_depth = 0;
// 构建三种括号的两两配对关系
vector<pair<char, char>> pairs = {{'(', ')'}, {'{', '}'}, {'[', ']'}};
// 若字符串长度为奇数，必定无法配对，isError设置为True
if (s.length() % 2 == 1) {
isError = true;
} else {
// 使用列表vector初始化一个空栈
vector<char> stack;
// 一次遍历字符串s中的每一个字符ch
for (char ch : s) {
// 若ch为某种左括号
if (ch == '(' || ch == '{' || ch == '[') {
// 则将ch加入栈顶，同时括号深度+1，更新最大括号深度
stack.push_back(ch);
cur_depth++;
ans = max(ans, cur_depth);
} else {
// 若此时栈为空
if (stack.empty()) {
// 该右括号无法与左括号配对，出现异常，isError设置为True，同时退出循环
isError = true;
break;
}
// 若栈不为空，则弹出栈顶字符，同时括号深度-1
char ch_stack_top = stack.back();
stack.pop_back();
cur_depth--;
// 若栈顶左括号字符ch_stack_top和当前右括号字符ch不配对，
// 出现异常，isError设置为True，同时退出循环
bool isPair = false;
for (auto pair : pairs) {
if (pair.first == ch_stack_top && pair.second == ch) {
isPair = true;
break;
}
}
if (!isPair) {
isError = true;
break;
}
}
}
// 经过一次遍历后，若仍存在元素，说明存在括号未配对，出现异常，isError设置为True
if (!stack.empty()) {
isError = true;
}
}
// 如果isError标志为True，说明前面某一步出现异常，输出0，否则输出最大深度ans
cout << (isError ? 0 : ans) << endl;
return 0;
}
时空复杂度
时间复杂度：O(N)。仅需一次遍历数组。
空间复杂度：O(N)。栈所占用的额外空间。
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
