【LeetCode 763】 划分字母区间 （中等）【贪心】

---

class Solution { public: vector<int> partitionLabels(string S) { vector<int> ans; int last[26]; fill(last,last+26,-1); for(int i=0;i<S.size();i++) //找到每个字母的最后出现位置 last[S[i]-'a']=i; int left=0,ll=0,right; //ll记录每次循环前left的位置 while(left<S.size()) { right=last[S[left]-'a']; //left位置字母的最后出现位置 while(left<right) { left++; if(last[S[left]-'a']>right) right=last[S[left]-'a']; //更新最右端的距离 } ans.push_back(right-ll+1); //长度 left=ll=right+1; //更新left距离 } return ans; } };