框架
1
2
3
4
5
6
| class Solution {
public:
vector<int> maxDepthAfterSplit(string seq) {
}
};
|
1. 直接模拟
首先遍历一遍获得最大深度maxDepth，若想令max(depth(A), depth(B))的可能取值最小，则结果必为(maxDepth+1)/2。
因此再次遍历序列，将深度小于最大深度一半的括号都分到A类中，之后的括号除去与A左括号匹配的右括号之外，其余全部放入B类中。
时间复杂度O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public:
vector<int> maxDepthAfterSplit(string seq) {
int n = seq.length();
int maxDepth = 0, curDepth = 0;
for (int i = 0; i < n; i++) {
if (seq[i] == '(')
curDepth++;
else {
maxDepth = maxDepth >= curDepth ? maxDepth : curDepth;
curDepth--;
}
}
int halfDepth = (maxDepth + 1) / 2;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
if (seq[i] == '(') {
curDepth++;
if (curDepth <= halfDepth)
ans[i] = 0;
else
ans[i] = 1;
}
else {
if (curDepth <= halfDepth)
ans[i] = 0;
else
ans[i] = 1;
curDepth--;
}
}
return ans;
}
};
|