题解 | #分品种#

考察的知识点：贪心；

解答方法分析：

1. 遍历字符串 s，记录每个字母最后出现的位置。
2. 使用双指针 start 和 end 表示当前片段的起始位置和结束位置，初始化为 0。
3. 再次遍历字符串 s，更新当前片段的结束位置 end如果当前位置 i 等于 end，则表示当前位置是段的结束位置，将当前片段的长度加入结果中，start 更新为 end+1，表示下一个片段的起始位置。
4. 返回结果。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型vector
     */
    vector<int> partitionLabels(string s) {
        vector<int> result;
        if (s.empty()) return result;
        int n = s.length();
        vector<int> last(26, 0);
        for (int i = 0; i < n; i++) {
            last[s[i] - 'a'] = i;
        }
        int start = 0;
        int end = 0;
        for (int i = 0; i < n; i++) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                result.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return result;
    }
};