leetcode-day10-划分字母区间[763题]

思路： 先找出每个元素出现的最后位置，这里使用对象的形式存放位置下标，因为对象key值的唯一性，得到一个存放最后下标位置的对象，定义两个指针a, b（变量），a一个用来放最大位置下标的值，b另个用来记录截取字符的开始位置，循环字符串，找出当前字符串的最后位置是否大于前一个最大位置下标，如果小于，则记录这个最大下标a = 最大的那个位置下标，直到循环到了和最大位置下标相等的那个元素，在此处截取字符串

考察的算法思想： 贪心算法 + 双指针

/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function(S) {
    if(S === null) return null;
    let len = S.length;
    const maxIndex = {};
    for (let i = 0; i < len; i++) { // 用对象来存放每个元素的位置，因为对象属性的唯一性，所以存最后一个位置
        maxIndex[S[i]] = i
    }
    console.log(maxIndex);
    const result = [];
    let start = 0;
    let end = 0;
    // 思路：遍历下字符串，只要当前字符的最后位置大于第一个元素的嘴一个元素的最后位置，就让这个end指向最大的最后位置下标，
    for (let i = 0; i < len; i++) {
        end = Math.max(end, maxIndex[S[i]]);
        console.log(i, end);
        // 这步特别重要，当遍历字符串的时候，遍历到最大的最后位置下标的时候，则该处就是分界线，将位置+1则为该处截取的字符串的长度
        // 下一个截取的字符串从该处+1的位置开始，所以要重置start
        if (i === end) { 
            result.push(end - start + 1);
            start = end + 1;
        }
    }

    return result;
};