力扣-贪心-763 划分字母区间

思路

先统计字符串中每一个字母出现的最后下标，然后从end初始化为第一个字母出现的最后下标，在i<=end时，不断更新end，因为一旦囊括新的字母就最起码要遍历到新字母出现的最后下标，在i>end时，说明遍历完成，再重新赋值end即可

代码

class Solution {
public:vector<int> partitionLabels(string s) {map<char, int> letterPos;for(int i = 0; i < s.size();i++){letterPos[s[i]] = i;}int end = letterPos[s[0]];vector<int> res;int length = 0;for (int i = 0; i < s.size(); i++) {if (i <= end) {length++;end = max(end, letterPos[s[i]]);} else {res.push_back(length);length = 1;end = letterPos[s[i]];}}res.push_back(length);return res;}
};