763. 划分字母区间
3 min
题目
解法：贪心
思路
核心思想是贪心策略：先统计每个字母的最后出现位置，再遍历字符串时维护当前片段的结束边界，当遍历到边界时立即切割。
正确性证明：对于任意片段，必须包含其中所有字母的最后出现位置，否则该字母会跨越片段。贪心策略选择当前已遍历字母的最后位置的最大值作为边界，确保边界内所有字母不会在后续出现，此时切割能得到最多片段数。若延迟切割只会减少片段数量，因此该策略是最优的。
- Step 1: 创建大小为26的数组
last，记录每个字母在字符串中最后出现的下标 - Step 2: 第一次遍历字符串，填充
last数组 - Step 3: 初始化
start=0、end=0，用于标记当前片段的起止位置 - Step 4: 第二次遍历字符串，更新
end = max(end, last[s[i]-'a']) - Step 5: 当
i == end时，说明当前片段结束，记录长度并更新start = end + 1
复杂度
- 时间复杂度: ，其中n为字符串长度，需要两次线性遍历
- 空间复杂度: ，使用了固定大小26的数组存储字母最后位置
代码
class Solution {
public:
vector<int> partitionLabels(string s) {
int last[26] = {0};
for(int i = 0; i < s.size(); i++){
last[s[i]-'a'] = i;
}
vector<int> ans;
int start = 0;
int end = 0;
for(int i = 0; i < s.size(); i++){
end = max(end,last[s[i]-'a']);
if(i == end){
ans.push_back(end - start + 1);
start = end + 1;
}
}
return ans;
}
};