双指针+贪心(思维)
思路
见: https://leetcode-cn.com/problems/partition-labels/solution/hua-fen-zi-mu-qu-jian-by-leetcode-solution/
和
https://leetcode-cn.com/problems/partition-labels/solution/tan-xin-si-lu-xiang-xi-zhu-shi-c-by-jian-ak6h/
代码
class Solution {
public:
vector<int> partitionLabels(string s) {
int end=0,start=0,map[26];
vector<int> ans;
for(int i=0;i<s.size();i++)
map[s[i]-'a']=i;
for(int i=0;i<s.size();i++)
{
end=max(end,map[s[i]-'a']);
if(i==end)
{
ans.push_back(end-start+1);
start=end+1;
}
}
return ans;
}
};