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' 。首先，对于一个符合要求的区间，区间内的所有字母的出现位置必会被包含在区间内，且该区间的最大下标会是区间内字母的最大下标位置。
我们使用 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 为官方的思路 ，具体做法与解法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; };