class Solution { public: vectorint partitionLabels(string s) { int last[26]; // 记录每个字母最后一次出现的位置 for(int i 0; i s.length(); i){ last[s[i] - a] i; } int start 0, end 0; vectorint res; for(int i start; i s.length(); i){ // 当前字母最后出现的位置决定区间至少要延伸到哪里 end max(end, last[s[i] - a]); // i走到了当前区间的最远位置可以进行切分 if(i end){ // 计算当前区间的长度 res.push_back(end - start 1); // 下一个区间从end的下一个位置开始 start end 1; } } return res; } };总结这道题的核心就是“记录最后位置 贪心划分区间”。1.last数组last[s[i] - a] i;记录每个字母最后一次出现的位置。例如s ababcbaca那么a 最后出现位置 8 b 最后出现位置 5 c 最后出现位置 72.end表示当前区间最远必须到哪里遍历当前区间时end max(end, last[s[i] - a]);看到一个字母就找到它最后一次出现的位置。如果这个位置比当前end更远就把end向后扩展。所以end可以理解成当前区间为了保证同一个字母不出现在其他区间最少需要到达的位置。3. 为什么i end就能切当i end说明当前已经走到了区间要求的最远位置。也就是说当前区间里面出现的所有字母在后面都不会再出现了。所以此时可以安全切分res.push_back(end - start 1);然后start end 1;开始下一个区间。4. 最核心的代码实际上整道题最重要的就三步end max(end, last[s[i] - a]);不断扩大区间。if(i end)发现可以切分。start end 1;进入下一个区间。一句话记忆先找每个字母最后出现的位置然后遍历字符串用end不断扩大当前区间当i走到end时说明区间已经完整可以切分。