【LeetCode】763. 划分字母区间（中等）——代码随想录算法训练营Day36

题目链接：763. 划分字母区间

题目描述

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

文章讲解：代码随想录

视频讲解：贪心算法，寻找最远的出现位置！ LeetCode：763.划分字母区间_哔哩哔哩_bilibili

题解1：贪心算法

思路：使用哈希表记录每个字母最后出现的位置。遍历字符串，同时更新右边界，当遍历的位置和右边界相同时，说明已经找到一个符合题目要求的区间，记录结果，然后更新左边界。局部最优为每次更新右边界为当前字母最后出现的位置，整体最优为划分最多的区间。

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function(s) {
    const res = [];
    const end = {}; // 哈希表记录每个字母最后出现的位置
    let left = 0, right = 0; // 记录区间的左右位置
    // 记录每个字母最后出现的位置
    for (let i = s.length - 1; i >= 0; i--) {
        if (!end[s[i]]) {
            end[s[i]] = i;
        }
    }
    for (let i = 0; i < s.length; i++) {
        right = Math.max(right, end[s[i]]); // 更新右边界
        if (right === i) {
            // 右边界和 i 相等
            res.push(right - left + 1); // 记录结果
            left = right + 1; // 更新左边界
        }
    }
    return res;
};

分析：时间复杂度为 O(n)，空间复杂度为 O(1)。

收获

这个题目也是一个重叠区间问题，每个区间的左右边界为这个字母最开始出现的位置和最后出现的位置。贪心算法求解重叠区间问题的步骤为先对区间按其中一个维度排序，本题的左边界已排序；然后每次遍历更新另一个维度，本题为更新右边界。