复盘 · LC 736 划分字母区间

题目

题号：LeetCode 736（国际站同题 763）
名称：划分字母区间（Partition Labels）
难度：Medium
链接：leetcode.cn/problems/partition-labels
今日代码：736-划分字母区间/index.js

题意

给定字符串 s，把它切成尽量多的连续片段，使得每个字母只出现在其中一个片段里。返回各片段长度组成的数组。

字母只含小写 a-z；s.length ≤ 500（中文站约束）。
划分方式唯一。
边界：单字符、全相同字母、每个字母只出现一次（每段长度 1）。

涉及算法

标签	一句话
哈希表	预处理每个字符的最后出现下标
贪心	从左扫，当前段右边界 = 段内所有字符「最后下标」的最大值；扫到右边界即切一刀
区间扩展	段内出现新字符时，右边界只能右扩不能左缩

教程对照：09 · 哈希表进阶（Map 存下标）+ 23 · 字符串常考（字符串单次扫描）。

评价我的解法

核心直觉对：先记录每个字符最后出现位置，再按段扩展边界。标准测例 ababcbacadefegdehijhklij → [9, 7, 8]、eccbbbbdec → [10] 均正确。

我的代码（摘自 736-划分字母区间/index.js，不含测例与注释）：

javascript

var partitionLabels = function (s) {
  const charList = s.split("");
  const letterMap = new Map();
  for (let i = 0; i < charList.length; i++) {
    const char = charList[i];
    letterMap.set(char, i);
  }
  let resultArr = [];
  let index = 0;
  while (index < charList.length) {
    const char = charList[index];
    const newIndex = letterMap.get(char);
    if (newIndex >= index) {
      let hasNext = true;
      let start = index;
      let end = newIndex;
      let lastPosition = newIndex;
      const charSet = new Set();
      while (hasNext) {
        hasNext = false;
        for (let i = start; i < end; i++) {
          charSet.add(charList[i]);
        }
        for (const c of charSet) {
          lastPosition = Math.max(letterMap.get(c), lastPosition);
        }
        if (lastPosition === newIndex) {
          break;
        }
        for (let i = newIndex + 1; i < lastPosition; i++) {
          const c = charList[i];
          const hasChar = charSet.has(c);
          if (!hasChar) {
            charSet.add(c);
            end = Math.max(end, letterMap.get(c));
            start = newIndex + 1;
            hasNext = true;
          }
        }
      }
      resultArr.push([index, lastPosition]);
      index = lastPosition + 1;
    }
  }
  return resultArr.map(([first, last]) => {
    return last - first + 1;
  });
};

对在哪：letterMap 存最后下标是正确预处理；外层 index = lastPosition + 1 切段逻辑与题意一致；结果数组再算长度也 OK。
糙在哪：
1. 实现绕远：贪心只需一次线性扫描维护 end = max(end, last[s[i]])，i === end 时切段；你用了「外层 while + 内层 hasNext + Set + 三重 for」，状态变量（start/end/newIndex/lastPosition/charSet）多，自己读都费劲。
2. 复杂度偏高：内层反复扫子区间、维护 Set，最坏可到 O(n²) 量级；LeetCode 提交约 8% 用时、7% 内存，说明常数与分配都偏大。
3. split("") 多余：直接 for (let i = 0; i < s.length; i++) 或 for (const ch of s) 即可，少一次 O(n) 数组拷贝。
4. if (newIndex >= index) 恒真：站在 index 处，该字符最后出现位置不可能小于当前下标，这层判断可删。

小结：思路能 AC，但还没沉淀成「一遍扫、一个 end」的贪心模板——面试里应优先讲标准写法。

最佳题解

预处理最后下标 + 单次贪心扫描：

javascript

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function (s) {
  const last = new Map();
  for (let i = 0; i < s.length; i++) {
    last.set(s[i], i);
  }
  const res = [];
  let start = 0;
  let end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last.get(s[i]));
    if (i === end) {
      res.push(end - start + 1);
      start = i + 1;
    }
  }
  return res;
};

时间 O(n)，空间 O(1)（字符集大小常数 26，Map 也算 O(1)）。
为何更优：每个下标只访问一次；i === end 即「当前段右边界已包住段内全部字符的最后出现」，与题意一一对应，无需 Set 反复合并。

关联题目

题	为何相关
56. 合并区间	区间右端点扩展、切段/合并的区间思维
435. 无重叠区间	贪心选区间端点，同类「区间调度」
452. 用最少数量的箭引爆气球	按右端点贪心，与「尽量多切 / 尽量少重叠」对照
55. 跳跃游戏	维护「当前能到达的最远边界」，与 `end = max(end, …)` 同构

一句话带走

划分字母区间 = 先存每个字符最后下标，再一遍扫：end 取 max，i 走到 end 就切一段。

复盘 · LC 736 划分字母区间 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​