763 划分字母区间
对于划分区间问题,我们通常会想到贪心
做法通常是比较区间的末端,更新区间
在本题中,分析题目:
- 同一字母最多出现在一个片段中 -> 假设字母出现的最后位置\(end_c\)为
last[s[i] - 'a'],区间末端\(end\)必须要大于等于\(end_c\),否则会出现两个字母出现在不同片段 - 把这个字符串划分为尽可能多的片段 -> 只要满足i到达区间末端\(end\),说明当前区间[start, end]所有字母出现的最后位置\(end_c\)为
last[s[i] - 'a'],都满足\(end_c\)小于等于区间末端\(end\),那么我们就可以立即划分区间,从而得到尽可能多的区间
class Solution {
public:
vector<int> partitionLabels(string s) {
int n = s.size();
int last[26];
vector<int> res;
// 统计每个字符最后出现的下标
for(int i = 0; i < n; i++){
last[s[i] - 'a'] = i;
}
// start为区间开始点,end为区间结束点
// end一定为某区间内所有last[j]的最大值
int start = 0, end = 0;
for(int i = 0; i < n; i++){
end = max(end, last[s[i] - 'a']);
// i == end 说明区间终点end已确定 且已遍历到区间终点end
if(i == end){
res.push_back(end - start + 1);
start = end + 1;
}
}
return res;
}
};
复杂度分析
时间复杂度:O(n),其中 n 是字符串的长度。需要遍历字符串两次,第一次遍历时记录每个字母最后一次出现的下标位置,第二次遍历时进行字符串的划分。
空间复杂度:O(∣Σ∣),其中 Σ 是字符串中的字符集。这道题中,字符串只包含小写字母,因此 ∣Σ∣=26。