贪心 - 划分字母区间

题目链接

class Solution { public: vector<int> partitionLabels(string S) { int n = S.size(); vector<int> pos(26, 0); // 记录每个字符最后出现的位置 for (int i = 0; i < n; ++i) { pos[S[i] - 'a'] = i; } vector<int> ret; int pre = 0; int t = pos[S[0] - 'a']; for (int i = 0; i < n; ++i) { if (t < i) { ret.push_back(i - pre); pre = i; } t = max(t, pos[S[i] - 'a']); } ret.push_back(n - pre); return ret; } };