当前位置:网站首页>栈题目:有效括号的嵌套深度
栈题目:有效括号的嵌套深度
2022-07-07 03:09:00 【伟大的车尔尼】
题目
标题和出处
标题:有效括号的嵌套深度
难度
6 级
题目描述
要求
一个字符串是有效括号字符串,当且仅当该字符串只包含 "(" \texttt{"("} "(" 和 ")" \texttt{")"} ")",且满足下列条件之一:
- 字符串是一个空字符串;
- 字符串可以写为 AB \texttt{AB} AB( A \texttt{A} A 与 B \texttt{B} B 字符串连接),其中 A \texttt{A} A 和 B \texttt{B} B 都是有效括号字符串;
- 字符串可以写为 (A) \texttt{(A)} (A),其中 A \texttt{A} A 是一个有效括号字符串。
对于有效括号字符串 S \texttt{S} S,其嵌套深度 depth(S) \texttt{depth(S)} depth(S) 定义如下:
- depth("") = 0 \texttt{depth("")} = 0 depth("")=0;
- depth(A + B) = max(depth(A), depth(B)) \texttt{depth(A + B) = max(depth(A), depth(B))} depth(A + B) = max(depth(A), depth(B)),其中 A \texttt{A} A 和 B \texttt{B} B 都是有效括号字符串;
- depth("(" + A + ")") = 1 + depth(A) \texttt{depth("(" + A + ")") = 1 + depth(A)} depth("(" + A + ")") = 1 + depth(A),其中 A \texttt{A} A 是一个有效括号字符串。
例如, "" \texttt{""} ""、 "()()" \texttt{"()()"} "()()" 和 "()(()())" \texttt{"()(()())"} "()(()())" 是有效括号字符串(嵌套深度分别是 0 \texttt{0} 0、 1 \texttt{1} 1 和 2 \texttt{2} 2), ")(" \texttt{")("} ")(" 和 "(()" \texttt{"(()"} "(()" 不是有效括号字符串。
给定一个有效括号字符串 seq \texttt{seq} seq,将其分成两个不相交的子序列 A \texttt{A} A 和 B \texttt{B} B,使得 A \texttt{A} A 和 B \texttt{B} B 是有效括号字符串,且 A.length + B.length = seq.length \texttt{A.length + B.length = seq.length} A.length + B.length = seq.length。
选择任意的 A \texttt{A} A 和 B \texttt{B} B 使得 max(depth(A), depth(B)) \texttt{max(depth(A), depth(B))} max(depth(A), depth(B)) 的值最小。
返回数组 answer \texttt{answer} answer(长度为 seq.length \texttt{seq.length} seq.length),表示选择 A \texttt{A} A 和 B \texttt{B} B 的编码:如果 seq[i] \texttt{seq[i]} seq[i] 分给 A \texttt{A} A 则 answer[i] = 0 \texttt{answer[i] = 0} answer[i] = 0,否则 answer[i] = 1 \texttt{answer[i] = 1} answer[i] = 1。如果存在多个满足要求的答案,只需返回其中任意一个即可。
示例
示例 1:
输入: seq = "(()())" \texttt{seq = "(()())"} seq = "(()())"
输出: [0,1,1,1,1,0] \texttt{[0,1,1,1,1,0]} [0,1,1,1,1,0]
示例 2:
输入: seq = "()(())()" \texttt{seq = "()(())()"} seq = "()(())()"
输出: [0,0,0,1,1,0,1,1] \texttt{[0,0,0,1,1,0,1,1]} [0,0,0,1,1,0,1,1]
数据范围
- 1 ≤ seq.size ≤ 10000 \texttt{1} \le \texttt{seq.size} \le \texttt{10000} 1≤seq.size≤10000
解法
思路和算法
在考虑将有效括号字符串分成两个不相交的子序列之前,首先需要考虑每个括号所在的嵌套深度。有效括号字符串中,每个左括号都有一个匹配的右括号,一对匹配的左右括号的嵌套深度相同。
为了计算每个括号所在的嵌套深度,可以使用栈存储左括号,根据栈内元素个数得到嵌套深度。从左到右遍历有效括号字符串 seq \textit{seq} seq,遇到左括号则将左括号入栈,遇到右括号则将栈顶的左括号出栈,表示当前的右括号和栈顶的左括号匹配。根据嵌套深度的定义,左括号和右括号的嵌套深度分别计算如下:
对于左括号,在入栈操作之后的栈内元素个数为左括号的嵌套深度;
对于右括号,在出栈操作之前的栈内元素个数为右括号的嵌套深度。
明确括号的嵌套深度的计算方法之后,回到原问题,将有效括号字符串 seq \textit{seq} seq 分成两个不相交的子序列 A A A 和 B B B,使得两个子序列的嵌套深度最小。只要栈内的一半括号属于子序列 A A A,另一半括号属于子序列 B B B,即可满足两个子序列的嵌套深度最小。实现方面,将奇数层的括号分给 A A A,将偶数层的括号分给 B B B 即可。
由于一对匹配的左右括号的嵌套深度相同,因此一对匹配的左右括号一定在同一个子序列中。由此可知,任意一个子序列中的左右括号数量一定相等,且左括号一定出现在与之匹配的右括号之前,因此两个子序列都是有效括号字符串。
由于栈内只存储左括号,因此并不需要真正维护一个栈,只需要记录遍历过程中的嵌套深度即可。
代码
class Solution {
public int[] maxDepthAfterSplit(String seq) {
int length = seq.length();
int[] answer = new int[length];
int depth = 0;
for (int i = 0; i < length; i++) {
if (seq.charAt(i) == '(') {
depth++;
answer[i] = depth % 2 == 1 ? 0 : 1;
} else {
answer[i] = depth % 2 == 1 ? 0 : 1;
depth--;
}
}
return answer;
}
}
复杂度分析
时间复杂度: O ( n ) O(n) O(n),其中 n n n 是字符串 seq \textit{seq} seq 的长度。需要遍历字符串 seq \textit{seq} seq 一次,每次更新嵌套深度的时间都是 O ( 1 ) O(1) O(1)。
空间复杂度: O ( 1 ) O(1) O(1)。除了返回值以外,使用的空间复杂度是常数。
边栏推荐
猜你喜欢
Anr principle and Practice
品牌电商如何逆势增长?在这里预见未来!
Unable to debug screen program with serial port
一文带你了解静态路由的特点、目的及配置基本功能示例
Apache ab 压力测试
「运维有小邓」符合GDPR的合规要求
Can't you really do it when you are 35 years old?
LM small programmable controller software (based on CoDeSys) Note 23: conversion of relative coordinates of servo motor operation (stepping motor) to absolute coordinates
【NOI模拟赛】区域划分(结论,构造)
Jetpack Compose 远不止是一个UI框架这么简单~
随机推荐
Brand · consultation standardization
一条慢SQL拖死整个系统
请教一个问题,flink oracle cdc,读取一个没有更新操作的表,隔十几秒就重复读取全量数据
当前发布的SKU(销售规格)信息中包含疑似与宝贝无关的字
MySQL user permissions
MYSQL----导入导出&视图&索引&执行计划
How to find the literature of a foreign language journal?
SVN version management in use replacement release and connection reset
Matlab tips (30) nonlinear fitting lsqcurefit
什么情况下考虑分库分表
多个kubernetes集群如何实现共享同一个存储
Redhat5 installing vmware tools under virtual machine
Apache ab 压力测试
Abnova 体外转录 mRNA工作流程和加帽方法介绍
Postgresql源码(60)事务系统总结
Stack and queue-p78-8 [2011 unified examination true question]
一文带你了解静态路由的特点、目的及配置基本功能示例
MATLAB小技巧(30)非线性拟合 lsqcurefit
隐马尔科夫模型(HMM)学习笔记
Anr principle and Practice