#P2983. 最大括号深度(100分)
-
1000ms
Tried: 535
Accepted: 145
Difficulty: 3
所属公司 :
华为od
最大括号深度(100分)
题面描述
给定一个仅由 (, ), {, }, [, ] 六种括号组成的字符串,判断该字符串是否为有效字符串。有效字符串的条件是:
- 每种类型的左右括号数量相等。
- 括号的闭合顺序正确(即先左后右)。
如果字符串有效,输出括号的最大嵌套深度;如果字符串无效,输出 0。
思路
-
栈的使用:我们可以使用栈来检查括号的有效性。遍历字符串时,遇到左括号就将其压入栈中,遇到右括号时检查栈顶的左括号是否与之匹配。如果匹配,则弹出栈顶元素;如果不匹配,则字符串无效。
-
深度计算:在遍历过程中,我们可以记录栈的最大深度,即为括号的最大嵌套深度。
-
无效情况:
- 如果遍历结束后栈不为空,说明有未匹配的左括号,字符串无效。
- 如果遇到右括号时栈为空,说明有未匹配的右括号,字符串无效。
cpp
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;
int maxDepth(string s) {
stack<char> st;
int max_depth = 0;
unordered_map<char, char> mapping = {{')', '('}, {']', '['}, {'}', '{'}};
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
max_depth = max(max_depth, (int)st.size());
} else if (c == ')' || c == ']' || c == '}') {
if (st.empty() || st.top() != mapping[c]) {
return 0;
}
st.pop();
}
}
return st.empty() ? max_depth : 0;
}
int main() {
string s;
cin >> s;
cout << maxDepth(s) << endl;
return 0;
}
python
def max_depth(s: str) -> int:
stack = []
max_depth = 0
mapping = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in mapping.values():
stack.append(char)
max_depth = max(max_depth, len(stack))
elif char in mapping.keys():
if not stack or stack[-1] != mapping[char]:
return 0
stack.pop()
return max_depth if not stack else 0
# 测试
s = input().strip()
print(max_depth(s))
java
import java.util.*;
public class Main {
public static int maxDepth(String s) {
Deque<Character> stack = new ArrayDeque<>();
int maxDepth = 0;
Map<Character, Character> mapping = new HashMap<>();
mapping.put(')', '(');
mapping.put(']', '[');
mapping.put('}', '{');
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
maxDepth = Math.max(maxDepth, stack.size());
} else if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty() || stack.peek() != mapping.get(c)) {
return 0;
}
stack.pop();
}
}
return stack.isEmpty() ? maxDepth : 0;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
System.out.println(maxDepth(s));
}
}
题目内容
现有一字符串仅由 ‘(‘,’)’,'{‘,’}’,'[‘,’]’六种括号组成。
若字符串满足以下条件之一,则为无效字符串:
①任一类型的左右括号数量不相等;
②存在未按正确顺序(先左后右)闭合的括号。
输出括号的最大嵌套深度,若字符串无效则输出0。
0≤字符串长度≤100000
输入描述
一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’的字符串
输出描述
一个整数,最大的括号深度
样例1
输入
[]
输出
1
说明
有效字符串,最大嵌套深度为1
样例2
输入
([]{()})
输出
3
说明
有效字符串,最大嵌套深度为3
样例3
输入
(]
输出
0
说明
无效字符串,有两种类型的左右括号数量不相等
样例4
输入
([)]
输出
0
说明
无效字符串,存在未按正确顺序闭合的括号
样例5
输入
)(
输出
0
说明
无效字符串,存在未按正确顺序闭合的括号。