：画地为牢的艺术——「划分字母区间」)
哈喽各位，我是前端小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; };深度图解
假设s = "abc...a..."(a 最后在 10)
i=0, char='a'。end变成 10。目前片段至少要到 10。i=1, char='b'。假如 'b' 最后在 5。max(10, 5)还是 10。没事。...
假如中间有个 'e' 最后在 15。那
end瞬间被撑大到 15。片段必须延长！当
i终于追上了end(比如走到 15 了)，说明前面所有人的要求都满足了。切！
复杂度分析
时间复杂度：O(N)
第一遍遍历统计位置 O(N)。
第二遍遍历寻找切割点 O(N)。
总共 O(N)。
空间复杂度：O(1)
虽然用了哈希表，但字符集大小固定是 26 个小写字母，所以空间是常数级的。
总结：边界的动态扩张
这道题展示了贪心算法处理**“动态约束”的能力。 最开始约束很小（只看第一个字母），随着遍历的进行，新加入的字母可能会“撑大”**这个约束（更新end）。我们只能顺从这个约束，直到我们走到了约束的尽头。
下一题预告：合并区间
接下来这道题LC 56. 合并区间，是区间问题的终极模板，也是面试中出现频率最高的题目之一（Top 3 级别）。
给你一堆乱序的区间
[1,3], [8,10], [2,6], [15,18]。让你把重叠的区间全部合并成一个大区间。
比如
[1,3]和[2,6]重叠，合并成[1,6]。
这道题和我们之前的“无重叠区间”逻辑正好相反，但操作手法（排序+更新边界）依然是熟悉的味道。
准备好进行最后的区间大一统了吗？下期见！
)
