- it技术
- LeetCode763. 划分字母区间
class Solution {
public:
vector
<int> partitionLabels(string S
) {
int n
= S
.size();
vector
<int> num
[26];
for (int i
= 0; i
< n
; i
++) {
num
[S
[i
] - 'a'].emplace_back(i
);
}
vector
<pair
<int, int>>s
;
for (int i
= 0; i
< 26; i
++)
if (num
[i
].size()) s
.emplace_back(pair
<int, int>{ num
[i
].front(), num
[i
].back() });
sort(s
.begin(), s
.end());
vector
<pair
<int, int>>ans
;
for (auto x
: s
) {
if (ans
.empty()) ans
.emplace_back(x
);
else if (x
.first
< ans
.back().second
)
ans
.back().second
= max(ans
.back().second
, x
.second
);
else ans
.emplace_back(x
);
}
vector
<int>anst
;
for (auto x
: ans
)
anst
.emplace_back(x
.second
- x
.first
+ 1);
return anst
;
}
};
