贪心算法专题(十三)：画地为牢的艺术——「划分字母区间」-编程实验室

哈喽各位，我是前端小L。

欢迎来到贪心算法专题第十三篇！题目给你一个字符串，让你把它切成尽可能多的片段。硬性要求：同一个字母只能出现在一个片段里。这意味着：如果第一段里有了 'a'，那么字符串里剩下的所有 'a' 都必须被关在第一段里，决不能跑出去。

力扣 763. 划分字母区间

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

题目分析：

输入：字符串s。
输出：一个数组，包含每个片段的长度。

例子：s = "ababcbacadefegdehijhklij"

我们看第一个字母a。它最后一次出现在下标8。
这意味着：第一段的结束位置，至少要是8。
但还没完！在0到8之间，我们还发现了b。b最后一次出现在下标5（在8以内，没事）。
我们还发现了c。c最后一次出现在下标7（在8以内，没事）。
所以，第一段就可以在下标8处切断。长度为9("ababcbaca")。
接下来看d...

核心思维：寻找“最远边界”

贪心策略非常直观：对于当前片段里的每一个字母，我都要确保它的“最后一次出现位置”在这个片段内。

这意味着，当前片段的结束边界 (end)，是由片段内所有字母的最后出现位置的最大值决定的。

步骤拆解：

预处理：我们需要知道每个字母“最后在哪里出现”。遍历一遍字符串，用一个哈希表（或数组）记录下来。
- 例如：map['a'] = 8,map['b'] = 5...
贪心遍历：
- 维护两个变量：start（当前片段起点），end（当前片段的最远边界）。
- 遍历字符串：
  - 对于当前字符c，更新end = Math.max(end, map[c])。
  - 关键判断：如果当前下标i走到了end，说明什么？
  - 说明在这个范围内出现的所有字母，它们的最后出现位置都在这里面了！再往后走就是全新的字母了。
  - 切断！记录长度end - start + 1。
  - 更新下一段的起点start = i + 1。

算法流程 (JavaScript)

统计最远位置：
- 创建一个对象或数组lastIndex。
- 遍历s，lastIndex[s[i]] = i。
双指针遍历：
- start = 0,end = 0。
- 遍历s(索引i)：
  - end = Math.max(end, lastIndex[s[i]])。
  - 如果i === end：
    - 收集结果：result.push(end - start + 1)。
    - 重置起点：start = i + 1。

代码实现

JavaScript

/** * @param {string} s * @return {number[]} */ var partitionLabels = function(s) { // 1. 记录每个字符最后出现的位置 // 用对象或者大小为26的数组都可以 const lastIndex = {}; for (let i = 0; i < s.length; i++) { lastIndex[s[i]] = i; } const result = []; let start = 0; // 当前片段的起始位置 let end = 0; // 当前片段的最远结束位置 // 2. 再次遍历，寻找切割点 for (let i = 0; i < s.length; i++) { // 贪心：不断扩展当前片段的边界 // 只要当前字符的最后出现位置比 end 大，就把 end 撑大 end = Math.max(end, lastIndex[s[i]]); // 如果遍历到了边界，说明这一段可以切了 if (i === end) { result.push(end - start + 1); // 记录长度 start = i + 1; // 准备开始下一段 } } return result; };