https://leetcode-cn.com/problems/partition-labels/

难度：中等

---

  字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

  示例 1：

  输入：S = "ababcbacadefegdehijhklij"

  输出：[9,7,8]

  解释：划分结果为 “ababcbaca”, “defegde”, “hijhklij”。每个字母最多出现在一个片段中。像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

提示：

• S的长度在[1, 500]之间。
• S只包含小写字母 'a' 到 'z' 。

解法1：记录最大最小下标

  首先，对于一个符合要求的区间，区间内的所有字母的出现位置必会被包含在区间内，且该区间的最大下标会是区间内字母的最大下标位置。

  我们使用 min 代表某个字母出现的最小下标，max 表示某个字母出现的最大下标，考虑一组字母：

a:{min: 0, max: 8}，b:{min: 1, max: 5}，c:{min: 4, max: 7}，d:{min: 9, max: 14}

  我们可以通过比较这些字母的最小、最大下标来寻找范围，范围的最小最大下标使用 gmin、gmax 来表示：

  从左到右遍历这组字母，首先令 gmin = a.min = 0，gmax = a.max = 8，对于接下来遍历到的每个字母，若 min 小于 gmax，则说明这两个字母会处在同一个范围内（因为它们的范围可能是相交的也可能是包含的，如 a 和 b 的范围是包含的，b 和 c 的范围是相交的），并更新范围的最大下标位置： gmax = Math.max(gmax, *.max)，这样，当遇到第一个不满足 min < gmax 的字母，说明该字母和当前范围内的字母不处于同一个范围，这时即可计算当前范围：gmax - gmin + 1，并重新赋值新的最大最小范围：gmax = *.max，gmin = *.min。

  需要注意的是，在遍历完所有字母后，还需要计算最后一个范围。

JS 代码如下：

/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function(S) {
    let chars = [];
    let res = [];

    for (let i = 0; i < S.length; i++) {
        let c = S[i];
        if (!chars[c]) {
            chars[c] = {
                min: i,
                max: i
            };
        } else {
            chars[c].min = Math.min(chars[c].min, i);
            chars[c].max = Math.max(chars[c].max, i);
        }
    }

    chars.sort((a, b) => {
        return a.min - b.min;
    });

    let min, max;
    for (let c in chars) {
        let char = chars[c];
        if (min === undefined) {
            min = char.min;
            max = char.max;
        } else if (char.min < max) {
            max = Math.max(max, char.max);
        } else {
            res.push(max - min + 1);
            min = char.min;
            max = char.max;
        }
    }
    
    res.push(max - min + 1);

    return res;
};

解法2：贪心

  解法2 为官方的思路 ，具体做法与解法1类似，不过会比较简洁。

  主要思路是先获取到所有字母的最大下标位置，然后遍历所有字母，不断更新最大下标位置 max，当遍历到了这个最大下标位置 max 时，就说明已遍历到的字母都在当前范围内了（因为对于每一个遍历的字母，都会比较字母的最大下标位置来更新范围的最大下标 max），这时候划分范围一定能得到最多的划分区域。

  获取范围还需要一个最小下标 min，min 初始时为 0，每当划分一个范围时，就更新 min 为 max + 1，代表下一个范围的最小下标。

JS 代码如下：

var partitionLabels = function(S) {
    let maxIndex = [], res = [];
    let max = 0, charCode = 'a'.charCodeAt();

    for (let i = 0; i < S.length; i++) {
        maxIndex[S.codePointAt(i) - charCode] = i;
    }

    let min = 0;
    for (let i = 0; i < S.length; i++) {
        max = Math.max(maxIndex[S.codePointAt(i) - charCode], max);
        if (i === max) {
            res.push(max - min + 1);
            min = i + 1;
        }
    }

    return res;
};