力扣热门100题之划分字母区间

张开发
• 2026/4/15 16:32:22 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

力扣热门100题之划分字母区间
核心思路先记录每个字母最后一次出现的下标遍历字符串不断更新当前片段的最远边界当遍历到边界时切割一次记录长度通俗解释第一步记录每个字母最后出现的位置比如ababcbacaa最后出现在 8b最后出现在 5c最后出现在 7这一步的目的只要这个字母在片段里出现整个片段必须覆盖到它最后一次出现的位置第二步遍历 贪心扩边界用end表示当前片段必须覆盖的最远位置遍历每一个字符不断把end往大扩当 i 走到 end 时说明这段覆盖了所有内部字符的最后位置可以切割第三步记录长度长度 end - start 1用示例走一遍输入ababcbacadefegdehijhklij前 9 个字符里所有字母的最后位置都 ≤ 8当 i8 时i end → 切割长度9接下来 7 个字符所有字母最后位置 ≤ 15i15 时切割长度7最后 8 个字符切割长度8最终结果[9,7,8]完整代码实现class Solution { public ListInteger partitionLabels(String s) { ListInteger res new ArrayList(); // 1. 记录每个字符最后出现的位置 int[] lastPos new int[26]; int n s.length(); for (int i 0; i n; i) { char c s.charAt(i); lastPos[c - a] i; } // 2. 贪心划分 int start 0; // 片段起始位置 int end 0; // 片段结束位置最远边界 for (int i 0; i n; i) { char c s.charAt(i); // 更新最远边界 end Math.max(end, lastPos[c - a]); // 当遍历到边界说明可以分割 if (i end) { res.add(end - start 1); start i 1; // 下一段的起点 } } return res; } }

更多文章