复盘 · LC 763 划分字母区间

题目

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

题意

给定字符串 s，把 s 划分成尽可能多的片段，使得同一字母最多出现在一个片段中。返回每个片段的长度。

例："ababcbacadefegdehijhklij" → [9,7,8]。
等价于：每个片段是「最小闭区间」，区间内出现的字母在整个 s 中的最后一次出现都不能越界。
边界：单字符；全相同字母 → 一个片段。

涉及算法

标签	一句话
贪心	扫一遍，维护当前段右边界 `end`
哈希表	预处理每个字符最后一次出现下标

思路与滑动窗口「扩右边界直到合法」类似，但本质是区间合并的贪心，不是 DP。

评价我的解法

代码与 8-25 同目录版本一致，能 AC，但用双层 while + Set 反复扩区间，可读性和常数都差一截；击败率个位数也侧面说明实现偏「重」。

我的代码（摘自 763-划分字母区间/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 存每个字符最后出现位置，这是贪心关键信息，第一步做对了。
扩区间直觉对：发现段内新字母就把右边界往后推——和「end = max(end, last[s[i]])」是同一逻辑，只是用 Set + 多重循环实现。
输出：先存 [start, end] 再算长度，结果正确。

糙在哪

复杂度常数大：段内反复扫 [start, end)、维护 charSet，最坏接近 O(n²)；标准贪心一遍 O(n)。
可读性：hasNext、newIndex、lastPosition 多层嵌套，自己 8-25、8-26 两天都难一眼看懂，维护成本高。
多余结构：split("") 可改为直接 s[i]；if (newIndex >= index) 在从左扫时恒成立。
未形成模板：面试更期望 10 行以内的「记录 last → 单遍扫描 end」。

小结：思路方向对（最后出现位置 + 扩边界），但实现是「把贪心写成了模拟器」。应默写标准一遍扫描，与今天复杂版对照口述差异。

最佳题解

一遍贪心（LeetCode 763 标准写法）：

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 字母）。
为何更优：i 走到当前段右边界 end 时，说明 [start, end] 已是极小合法段，直接切分；无需 Set 反复扩。

关联题目

题	为何相关
56. 合并区间	同样是「扩边界 / 合并区间」贪心
435. 无重叠区间	区间调度，贪心选右端点
76. 最小覆盖子串	也维护窗口右边界，但是滑窗 + 计数

一句话带走

划分字母区间：先记录每个字母最后位置，从左扫 end = max(end, last[s[i]])，当 i === end 就切一段。

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

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​