目录1. 问题描述2. 问题分析2.1 题目理解2.2 核心洞察2.3 破题关键3. 算法设计与实现3.1 解法一标准贪心一次遍历 最后位置数组3.2 解法二区间合并思路显式构建区间3.3 解法三贪心 哈希表Java 8 流式写法3.4 解法四双指针 前缀最远位置进阶优化3.5 解法五递归分治另一种思维4. 性能对比4.1 理论复杂度对比表4.2 实际性能测试4.3 各场景适用性分析5. 扩展与变体5.1 变体一划分字母区间但允许重新排列片段5.2 变体二划分字母区间并返回片段内容5.3 变体三包含大写字母和数字的扩展字符集5.4 变体四求划分后片段的最大长度6. 总结6.1 核心思想总结6.2 实际应用场景6.3 面试建议6.4 常见面试问题 QA1. 问题描述给你一个字符串s。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。例如字符串ababcc能够被分为[abab, cc]但类似[aba, bcc]或[ab, ab, cc]的划分是非法的。注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是s。返回一个表示每个字符串片段的长度的列表。示例 1输入s ababcbacadefegdehijhklij 输出[9,7,8] 解释 划分结果为 ababcbaca、defegde、hijhklij 。 每个字母最多出现在一个片段中。 像 ababcbacadefegde, hijhklij 这样的划分是错误的因为划分的片段数较少。示例 2输入s eccbbbbdec 输出[10]提示1 s.length 500 s 仅由小写英文字母组成2. 问题分析2.1 题目理解本题要求将原字符串切分成若干连续的子串满足每个子串内部出现的所有字母在整个字符串的其他子串中不再出现。划分后拼接顺序不变且要求划分出的片段数尽可能多。等价于找到一组最小的划分点使得每个片段内的字符集合与其他片段不重叠。2.2 核心洞察关键性质对于任意字母c如果它出现在多个位置那么这些位置必须落在同一个片段中。因此每个片段的右边界至少应覆盖该片段内所有字母的最后一次出现位置。贪心策略从左到右扫描维护当前片段的“最远右边界”。当扫描到当前片段的最远右边界时当前片段结束即可切分。2.3 破题关键预先计算每个字母在字符串中最后一次出现的下标。使用双指针start表示当前片段起始位置end表示当前片段的理论最远边界。遍历过程中不断更新end max(end, last[s[i]])当i end时说明当前片段已经闭合记录长度end - start 1并更新start end 1。3. 算法设计与实现3.1 解法一标准贪心一次遍历 最后位置数组核心思想利用字符最后一次出现的位置来动态扩展当前片段的右边界当遍历到右边界时完成一个片段。算法思路遍历字符串记录每个字母最后一次出现的索引。再次遍历字符串维护当前片段的起始start和当前最远右边界end。对于每个字符s[i]更新end max(end, last[s[i]])。如果i end说明当前片段已结束记录长度并更新start i 1。Java代码实现importjava.util.*;publicclassPartitionLabels{publicListIntegerpartitionLabels(Strings){int[]lastnewint[26];intns.length();// 记录每个字母最后出现的位置for(inti0;in;i){last[s.charAt(i)-a]i;}ListIntegerresultnewArrayList();intstart0,end0;for(inti0;in;i){endMath.max(end,last[s.charAt(i)-a]);if(iend){result.add(end-start1);starti1;}}returnresult;}}性能分析时间复杂度O(n)其中 n 为字符串长度。两次遍历常数开销。空间复杂度O(1) 或 O(Σ)Σ 为字符集大小26可视为常数。3.2 解法二区间合并思路显式构建区间核心思想将每个字符的第一次出现和最后一次出现视作一个区间问题转化为合并重叠区间最后计算每个合并区间的长度。算法思路为每个字母构建一个区间[first, last]。将这些区间按起始位置排序实际上字母顺序天然有序但需考虑未出现字母。合并重叠区间得到合并后的区间列表。每个合并区间的长度即为一个片段的长度。Java代码实现importjava.util.*;publicclassPartitionLabelsInterval{publicListIntegerpartitionLabels(Strings){intns.length();// 记录每个字母的首次和末次出现位置初始化为 -1int[]firstnewint[26];int[]lastnewint[26];Arrays.fill(first,-1);Arrays.fill(last,-1);for(inti0;in;i){intidxs.charAt(i)-a;if(first[idx]-1)first[idx]i;last[idx]i;}// 收集所有出现的区间Listint[]intervalsnewArrayList();for(inti0;i26;i){if(first[i]!-1){intervals.add(newint[]{first[i],last[i]});}}// 按起始位置排序intervals.sort((a,b)-a[0]-b[0]);ListIntegerresultnewArrayList();int[]curintervals.get(0);for(inti1;iintervals.size();i){int[]nextintervals.get(i);if(next[0]cur[1]){// 重叠合并cur[1]Math.max(cur[1],next[1]);}else{// 不重叠记录当前区间长度result.add(cur[1]-cur[0]1);curnext;}}result.add(cur[1]-cur[0]1);returnresult;}}性能分析时间复杂度O(n Σ log Σ)n 为字符串长度Σ 为字符集大小26排序可视为常数。空间复杂度O(Σ)用于存储区间可视为常数。3.3 解法三贪心 哈希表Java 8 流式写法核心思想使用MapCharacter, Integer记录每个字符的最后出现位置其余逻辑与解法一相同但代码更具可读性适用于字符集不确定的场景。算法思路用哈希表存储每个字符最后出现的位置。遍历字符串动态维护当前片段的右边界。当到达右边界时切分。Java代码实现importjava.util.*;publicclassPartitionLabelsMap{publicListIntegerpartitionLabels(Strings){MapCharacter,IntegerlastnewHashMap();for(inti0;is.length();i){last.put(s.charAt(i),i);}ListIntegerresultnewArrayList();intstart0,end0;for(inti0;is.length();i){endMath.max(end,last.get(s.charAt(i)));if(iend){result.add(end-start1);starti1;}}returnresult;}}性能分析时间复杂度O(n)哈希表操作 O(1)。空间复杂度O(Σ)哈希表大小最多为字符种类数。3.4 解法四双指针 前缀最远位置进阶优化核心思想在单次遍历中直接构造结果无需显式存储last数组而是利用一个额外数组实时更新。算法思路创建一个长度为 26 的数组初始化全部为 0。第一次遍历记录每个字符最后一次出现的位置。第二次遍历利用指针i和jj表示当前片段的右边界i是当前扫描位置。每当i j时记录长度并重置起始位置。Java代码实现与解法一本质相同此处展示另一种写法importjava.util.*;publicclassPartitionLabelsTwoPointer{publicListIntegerpartitionLabels(Strings){int[]lastnewint[26];for(inti0;is.length();i){last[s.charAt(i)-a]i;}ListIntegerresultnewArrayList();intstart0,end0;for(inti0;is.length();i){endMath.max(end,last[s.charAt(i)-a]);if(iend){result.add(end-start1);starti1;}}returnresult;}}性能分析时间复杂度O(n)空间复杂度O(1)3.5 解法五递归分治另一种思维核心思想将问题转化为对于每个字符它的片段必须覆盖它所有出现的位置。可以递归地处理找到第一个字符确定它的最远右边界然后检查该边界内的所有字符若某个字符的最远出现位置超过当前边界则扩展边界直到边界内所有字符的最后出现位置都不超过边界然后递归处理剩余部分。算法思路定义递归函数partition(start, end)但这里我们采用迭代模拟递归的方式。从索引i0开始取s[i]的最远位置last[s[i]]作为当前边界bound。遍历[i, bound]区间内的字符不断更新bound max(bound, last[s[k]])。当遍历完区间后该区间即为一个合法片段记录长度然后i bound 1继续。Java代码实现importjava.util.*;publicclassPartitionLabelsRecursive{publicListIntegerpartitionLabels(Strings){int[]lastnewint[26];for(inti0;is.length();i){last[s.charAt(i)-a]i;}ListIntegerresultnewArrayList();inti0;while(is.length()){intboundlast[s.charAt(i)-a];intji;while(jbound){boundMath.max(bound,last[s.charAt(j)-a]);j;}result.add(j-i);ij;}returnresult;}}性能分析时间复杂度O(n)每个字符最多被访问两次。空间复杂度O(1)4. 性能对比4.1 理论复杂度对比表解法时间复杂度空间复杂度特点解法一标准贪心O(n)O(1)最简洁推荐解法二区间合并O(n Σ log Σ)O(Σ)直观易理解解法三哈希表O(n)O(Σ)通用性强解法四双指针O(n)O(1)与解法一同质解法五递归分治O(n)O(1)逻辑稍显复杂但无误4.2 实际性能测试以 LeetCode 官方测试用例长度 500 以内的字符串为例所有解法均能在 1ms 内完成。对于超长字符串如 10^5 长度解法一、四、五仍然保持 O(n) 性能解法二的排序常数项略高解法三因哈希表开销稍慢但仍可接受。实际工程中推荐使用解法一或四。4.3 各场景适用性分析小字符集如仅小写字母解法一、四最合适数组访问极快。字符集不确定或较大解法三哈希表更具扩展性。需要展示算法推导过程解法二区间合并有助于理解“片段由多个字符区间合并而成”的本质。递归思维练习解法五展示了另一种分治思路适合教学。5. 扩展与变体5.1 变体一划分字母区间但允许重新排列片段题目描述给定字符串 s允许将片段任意重排后拼接要求每个字母只出现在一个片段中求最大片段数。此时只需统计每个字母的出现次数每个字母可以单独成为一个片段片段数为不同字母的个数。代码实现非常简单。Java代码实现publicintmaxPartitionsByRearrangement(Strings){SetCharactersetnewHashSet();for(charc:s.toCharArray())set.add(c);returnset.size();}5.2 变体二划分字母区间并返回片段内容题目描述在划分片段的基础上不仅返回长度还要返回每个片段的具体子串。只需在切分时记录子串即可。Java代码实现publicListStringpartitionLabelsWithContent(Strings){int[]lastnewint[26];for(inti0;is.length();i)last[s.charAt(i)-a]i;ListStringresultnewArrayList();intstart0,end0;for(inti0;is.length();i){endMath.max(end,last[s.charAt(i)-a]);if(iend){result.add(s.substring(start,end1));starti1;}}returnresult;}5.3 变体三包含大写字母和数字的扩展字符集题目描述字符串可能包含大写字母和数字仍要求划分尽可能多的片段。解决方案只需将last数组大小扩大至 ASCII 范围如 128 或 256或使用哈希表。Java代码实现publicListIntegerpartitionLabelsExtended(Strings){int[]lastnewint[128];// ASCII 可包含所有常见字符for(inti0;is.length();i)last[s.charAt(i)]i;ListIntegerresultnewArrayList();intstart0,end0;for(inti0;is.length();i){endMath.max(end,last[s.charAt(i)]);if(iend){result.add(end-start1);starti1;}}returnresult;}5.4 变体四求划分后片段的最大长度题目描述在满足划分条件的前提下求出所有片段中长度的最大值。Java代码实现publicintmaxPartitionLength(Strings){int[]lastnewint[26];for(inti0;is.length();i)last[s.charAt(i)-a]i;intmaxLen0;intstart0,end0;for(inti0;is.length();i){endMath.max(end,last[s.charAt(i)-a]);if(iend){maxLenMath.max(maxLen,end-start1);starti1;}}returnmaxLen;}6. 总结6.1 核心思想总结划分字母区间的本质是“区间合并”问题。每个字母定义了一个必须包含其所有出现位置的最小区间这些区间相互重叠的部分必须合并。通过贪心策略我们可以在一次遍历中完成合并和切分时间复杂度 O(n)空间复杂度 O(1)。6.2 实际应用场景文本分段根据关键词出现位置将文档划分为独立段落。资源分组在分布式系统中将关联紧密的任务划分到同一节点。代码重构识别代码中变量作用域划分独立模块。6.3 面试建议面试时首选解法一贪心数组简洁高效。解释时强调“最远右边界”的动态维护并说明为什么贪心能保证片段数最多因为每次切分都尽可能早地结束片段。可以补充说明如果字符集很大该如何改进使用哈希表。准备回答时间复杂度、空间复杂度分析以及为什么算法是正确的。6.4 常见面试问题 QAQ1为什么贪心算法能得到最多的片段数A贪心策略在每一次遇到当前片段的最远边界时就立即切分这样不会错过任何可能的切分点因为任何更早的切分都会导致某个字母跨越片段而任何更晚的切分都会减少片段数量。Q2如果字符串长度非常大例如 10^7这个算法还适用吗A适用因为算法只进行了两次线性扫描且只使用了常数级额外空间。只需将int[]替换为更高效的结构或直接使用 ASCII 数组性能依然优异。Q3如果字符不只小写字母而是 Unicode该如何处理A可以使用哈希表如 Java 的HashMapCharacter, Integer记录最后出现位置时间复杂度仍为 O(n)空间复杂度 O(k)k 为不同字符数。Q4是否有更复杂的变体比如允许在片段间添加分隔符A是的某些变体会要求输出添加分隔符后的字符串核心算法不变只需在切分点插入分隔符即可。
LeetCode经典算法面试题 #763：划分字母区间（贪心法、区间合并、递归分治等多种实现方案详解）
发布时间：2026/7/29 3:58:46
目录1. 问题描述2. 问题分析2.1 题目理解2.2 核心洞察2.3 破题关键3. 算法设计与实现3.1 解法一标准贪心一次遍历 最后位置数组3.2 解法二区间合并思路显式构建区间3.3 解法三贪心 哈希表Java 8 流式写法3.4 解法四双指针 前缀最远位置进阶优化3.5 解法五递归分治另一种思维4. 性能对比4.1 理论复杂度对比表4.2 实际性能测试4.3 各场景适用性分析5. 扩展与变体5.1 变体一划分字母区间但允许重新排列片段5.2 变体二划分字母区间并返回片段内容5.3 变体三包含大写字母和数字的扩展字符集5.4 变体四求划分后片段的最大长度6. 总结6.1 核心思想总结6.2 实际应用场景6.3 面试建议6.4 常见面试问题 QA1. 问题描述给你一个字符串s。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。例如字符串ababcc能够被分为[abab, cc]但类似[aba, bcc]或[ab, ab, cc]的划分是非法的。注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是s。返回一个表示每个字符串片段的长度的列表。示例 1输入s ababcbacadefegdehijhklij 输出[9,7,8] 解释 划分结果为 ababcbaca、defegde、hijhklij 。 每个字母最多出现在一个片段中。 像 ababcbacadefegde, hijhklij 这样的划分是错误的因为划分的片段数较少。示例 2输入s eccbbbbdec 输出[10]提示1 s.length 500 s 仅由小写英文字母组成2. 问题分析2.1 题目理解本题要求将原字符串切分成若干连续的子串满足每个子串内部出现的所有字母在整个字符串的其他子串中不再出现。划分后拼接顺序不变且要求划分出的片段数尽可能多。等价于找到一组最小的划分点使得每个片段内的字符集合与其他片段不重叠。2.2 核心洞察关键性质对于任意字母c如果它出现在多个位置那么这些位置必须落在同一个片段中。因此每个片段的右边界至少应覆盖该片段内所有字母的最后一次出现位置。贪心策略从左到右扫描维护当前片段的“最远右边界”。当扫描到当前片段的最远右边界时当前片段结束即可切分。2.3 破题关键预先计算每个字母在字符串中最后一次出现的下标。使用双指针start表示当前片段起始位置end表示当前片段的理论最远边界。遍历过程中不断更新end max(end, last[s[i]])当i end时说明当前片段已经闭合记录长度end - start 1并更新start end 1。3. 算法设计与实现3.1 解法一标准贪心一次遍历 最后位置数组核心思想利用字符最后一次出现的位置来动态扩展当前片段的右边界当遍历到右边界时完成一个片段。算法思路遍历字符串记录每个字母最后一次出现的索引。再次遍历字符串维护当前片段的起始start和当前最远右边界end。对于每个字符s[i]更新end max(end, last[s[i]])。如果i end说明当前片段已结束记录长度并更新start i 1。Java代码实现importjava.util.*;publicclassPartitionLabels{publicListIntegerpartitionLabels(Strings){int[]lastnewint[26];intns.length();// 记录每个字母最后出现的位置for(inti0;in;i){last[s.charAt(i)-a]i;}ListIntegerresultnewArrayList();intstart0,end0;for(inti0;in;i){endMath.max(end,last[s.charAt(i)-a]);if(iend){result.add(end-start1);starti1;}}returnresult;}}性能分析时间复杂度O(n)其中 n 为字符串长度。两次遍历常数开销。空间复杂度O(1) 或 O(Σ)Σ 为字符集大小26可视为常数。3.2 解法二区间合并思路显式构建区间核心思想将每个字符的第一次出现和最后一次出现视作一个区间问题转化为合并重叠区间最后计算每个合并区间的长度。算法思路为每个字母构建一个区间[first, last]。将这些区间按起始位置排序实际上字母顺序天然有序但需考虑未出现字母。合并重叠区间得到合并后的区间列表。每个合并区间的长度即为一个片段的长度。Java代码实现importjava.util.*;publicclassPartitionLabelsInterval{publicListIntegerpartitionLabels(Strings){intns.length();// 记录每个字母的首次和末次出现位置初始化为 -1int[]firstnewint[26];int[]lastnewint[26];Arrays.fill(first,-1);Arrays.fill(last,-1);for(inti0;in;i){intidxs.charAt(i)-a;if(first[idx]-1)first[idx]i;last[idx]i;}// 收集所有出现的区间Listint[]intervalsnewArrayList();for(inti0;i26;i){if(first[i]!-1){intervals.add(newint[]{first[i],last[i]});}}// 按起始位置排序intervals.sort((a,b)-a[0]-b[0]);ListIntegerresultnewArrayList();int[]curintervals.get(0);for(inti1;iintervals.size();i){int[]nextintervals.get(i);if(next[0]cur[1]){// 重叠合并cur[1]Math.max(cur[1],next[1]);}else{// 不重叠记录当前区间长度result.add(cur[1]-cur[0]1);curnext;}}result.add(cur[1]-cur[0]1);returnresult;}}性能分析时间复杂度O(n Σ log Σ)n 为字符串长度Σ 为字符集大小26排序可视为常数。空间复杂度O(Σ)用于存储区间可视为常数。3.3 解法三贪心 哈希表Java 8 流式写法核心思想使用MapCharacter, Integer记录每个字符的最后出现位置其余逻辑与解法一相同但代码更具可读性适用于字符集不确定的场景。算法思路用哈希表存储每个字符最后出现的位置。遍历字符串动态维护当前片段的右边界。当到达右边界时切分。Java代码实现importjava.util.*;publicclassPartitionLabelsMap{publicListIntegerpartitionLabels(Strings){MapCharacter,IntegerlastnewHashMap();for(inti0;is.length();i){last.put(s.charAt(i),i);}ListIntegerresultnewArrayList();intstart0,end0;for(inti0;is.length();i){endMath.max(end,last.get(s.charAt(i)));if(iend){result.add(end-start1);starti1;}}returnresult;}}性能分析时间复杂度O(n)哈希表操作 O(1)。空间复杂度O(Σ)哈希表大小最多为字符种类数。3.4 解法四双指针 前缀最远位置进阶优化核心思想在单次遍历中直接构造结果无需显式存储last数组而是利用一个额外数组实时更新。算法思路创建一个长度为 26 的数组初始化全部为 0。第一次遍历记录每个字符最后一次出现的位置。第二次遍历利用指针i和jj表示当前片段的右边界i是当前扫描位置。每当i j时记录长度并重置起始位置。Java代码实现与解法一本质相同此处展示另一种写法importjava.util.*;publicclassPartitionLabelsTwoPointer{publicListIntegerpartitionLabels(Strings){int[]lastnewint[26];for(inti0;is.length();i){last[s.charAt(i)-a]i;}ListIntegerresultnewArrayList();intstart0,end0;for(inti0;is.length();i){endMath.max(end,last[s.charAt(i)-a]);if(iend){result.add(end-start1);starti1;}}returnresult;}}性能分析时间复杂度O(n)空间复杂度O(1)3.5 解法五递归分治另一种思维核心思想将问题转化为对于每个字符它的片段必须覆盖它所有出现的位置。可以递归地处理找到第一个字符确定它的最远右边界然后检查该边界内的所有字符若某个字符的最远出现位置超过当前边界则扩展边界直到边界内所有字符的最后出现位置都不超过边界然后递归处理剩余部分。算法思路定义递归函数partition(start, end)但这里我们采用迭代模拟递归的方式。从索引i0开始取s[i]的最远位置last[s[i]]作为当前边界bound。遍历[i, bound]区间内的字符不断更新bound max(bound, last[s[k]])。当遍历完区间后该区间即为一个合法片段记录长度然后i bound 1继续。Java代码实现importjava.util.*;publicclassPartitionLabelsRecursive{publicListIntegerpartitionLabels(Strings){int[]lastnewint[26];for(inti0;is.length();i){last[s.charAt(i)-a]i;}ListIntegerresultnewArrayList();inti0;while(is.length()){intboundlast[s.charAt(i)-a];intji;while(jbound){boundMath.max(bound,last[s.charAt(j)-a]);j;}result.add(j-i);ij;}returnresult;}}性能分析时间复杂度O(n)每个字符最多被访问两次。空间复杂度O(1)4. 性能对比4.1 理论复杂度对比表解法时间复杂度空间复杂度特点解法一标准贪心O(n)O(1)最简洁推荐解法二区间合并O(n Σ log Σ)O(Σ)直观易理解解法三哈希表O(n)O(Σ)通用性强解法四双指针O(n)O(1)与解法一同质解法五递归分治O(n)O(1)逻辑稍显复杂但无误4.2 实际性能测试以 LeetCode 官方测试用例长度 500 以内的字符串为例所有解法均能在 1ms 内完成。对于超长字符串如 10^5 长度解法一、四、五仍然保持 O(n) 性能解法二的排序常数项略高解法三因哈希表开销稍慢但仍可接受。实际工程中推荐使用解法一或四。4.3 各场景适用性分析小字符集如仅小写字母解法一、四最合适数组访问极快。字符集不确定或较大解法三哈希表更具扩展性。需要展示算法推导过程解法二区间合并有助于理解“片段由多个字符区间合并而成”的本质。递归思维练习解法五展示了另一种分治思路适合教学。5. 扩展与变体5.1 变体一划分字母区间但允许重新排列片段题目描述给定字符串 s允许将片段任意重排后拼接要求每个字母只出现在一个片段中求最大片段数。此时只需统计每个字母的出现次数每个字母可以单独成为一个片段片段数为不同字母的个数。代码实现非常简单。Java代码实现publicintmaxPartitionsByRearrangement(Strings){SetCharactersetnewHashSet();for(charc:s.toCharArray())set.add(c);returnset.size();}5.2 变体二划分字母区间并返回片段内容题目描述在划分片段的基础上不仅返回长度还要返回每个片段的具体子串。只需在切分时记录子串即可。Java代码实现publicListStringpartitionLabelsWithContent(Strings){int[]lastnewint[26];for(inti0;is.length();i)last[s.charAt(i)-a]i;ListStringresultnewArrayList();intstart0,end0;for(inti0;is.length();i){endMath.max(end,last[s.charAt(i)-a]);if(iend){result.add(s.substring(start,end1));starti1;}}returnresult;}5.3 变体三包含大写字母和数字的扩展字符集题目描述字符串可能包含大写字母和数字仍要求划分尽可能多的片段。解决方案只需将last数组大小扩大至 ASCII 范围如 128 或 256或使用哈希表。Java代码实现publicListIntegerpartitionLabelsExtended(Strings){int[]lastnewint[128];// ASCII 可包含所有常见字符for(inti0;is.length();i)last[s.charAt(i)]i;ListIntegerresultnewArrayList();intstart0,end0;for(inti0;is.length();i){endMath.max(end,last[s.charAt(i)]);if(iend){result.add(end-start1);starti1;}}returnresult;}5.4 变体四求划分后片段的最大长度题目描述在满足划分条件的前提下求出所有片段中长度的最大值。Java代码实现publicintmaxPartitionLength(Strings){int[]lastnewint[26];for(inti0;is.length();i)last[s.charAt(i)-a]i;intmaxLen0;intstart0,end0;for(inti0;is.length();i){endMath.max(end,last[s.charAt(i)-a]);if(iend){maxLenMath.max(maxLen,end-start1);starti1;}}returnmaxLen;}6. 总结6.1 核心思想总结划分字母区间的本质是“区间合并”问题。每个字母定义了一个必须包含其所有出现位置的最小区间这些区间相互重叠的部分必须合并。通过贪心策略我们可以在一次遍历中完成合并和切分时间复杂度 O(n)空间复杂度 O(1)。6.2 实际应用场景文本分段根据关键词出现位置将文档划分为独立段落。资源分组在分布式系统中将关联紧密的任务划分到同一节点。代码重构识别代码中变量作用域划分独立模块。6.3 面试建议面试时首选解法一贪心数组简洁高效。解释时强调“最远右边界”的动态维护并说明为什么贪心能保证片段数最多因为每次切分都尽可能早地结束片段。可以补充说明如果字符集很大该如何改进使用哈希表。准备回答时间复杂度、空间复杂度分析以及为什么算法是正确的。6.4 常见面试问题 QAQ1为什么贪心算法能得到最多的片段数A贪心策略在每一次遇到当前片段的最远边界时就立即切分这样不会错过任何可能的切分点因为任何更早的切分都会导致某个字母跨越片段而任何更晚的切分都会减少片段数量。Q2如果字符串长度非常大例如 10^7这个算法还适用吗A适用因为算法只进行了两次线性扫描且只使用了常数级额外空间。只需将int[]替换为更高效的结构或直接使用 ASCII 数组性能依然优异。Q3如果字符不只小写字母而是 Unicode该如何处理A可以使用哈希表如 Java 的HashMapCharacter, Integer记录最后出现位置时间复杂度仍为 O(n)空间复杂度 O(k)k 为不同字符数。Q4是否有更复杂的变体比如允许在片段间添加分隔符A是的某些变体会要求输出添加分隔符后的字符串核心算法不变只需在切分点插入分隔符即可。
