给定 有效括号字符串 s,返回 s 的 嵌套深度。嵌套深度是嵌套括号的 最大 数量。
示例 1:
输入:s = “(1+(2*3)+((8)/4))+1”
输出:3
解释:数字 8 在嵌套的 3 层括号中。
示例 2:
输入:s = “(1)+((2))+(((3)))”
输出:3
解释:数字 3 在嵌套的 3 层括号中。
示例 3:
输入:s = “()(())((()()))”
输出:3
提示:
1 <= s.length <= 100
s 由数字 0-9 和字符 ‘+’、‘-’、‘*’、‘/’、‘(’、‘)’ 组成
题目数据保证括号字符串 s 是 有效的括号字符串
遍历
class Solution {
public:int maxDepth(string s) {int left = 0;int res = 0;for(char c : s){if(c == '('){left++;res = max(res, left);}else if(c == ')'){left--;}}return res;}
};
时间复杂度:O(n),其中 n 是字符串 s 的长度。
空间复杂度:O(1)。我们只需要常数空间来存放若干变量。
这道题很简单,我们用left来记录左括号的数量,然后每当遍历到一个右括号,就会匹配一个左括号,然后令未匹配的左括号数量–,我们通过res来记录未匹配左括号的最多的数量,res即是括号的最大嵌套深度。