文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题划分字母区间出处763. 划分字母区间难度4 级题目描述要求给定字符串s \texttt{s}s。需要将这个字符串划分为尽可能多的片段满足同一字母最多出现在一个片段中。注意在将字符串划分成片段之后所有片段拼接之后的结果应该是s \texttt{s}s。返回一个表示每个片段的长度的列表。示例示例 1输入s ababcbacadefegdehijhklij \texttt{s ababcbacadefegdehijhklij}s ababcbacadefegdehijhklij输出[9,7,8] \texttt{[9,7,8]}[9,7,8]解释划分结果为[ababcbaca, defegde, hijhklij] \texttt{[ababcbaca, defegde, hijhklij]}[ababcbaca, defegde, hijhklij]。每个字母最多出现在一个片段中。像[ababcbacadefegde, hijhklij] \texttt{[ababcbacadefegde, hijhklij]}[ababcbacadefegde, hijhklij]的划分是错误的因为划分的片段数较少。示例 2输入s eccbbbbdec \texttt{s eccbbbbdec}s eccbbbbdec输出[10] \texttt{[10]}[10]数据范围1 ≤ s.length ≤ 500 \texttt{1} \le \texttt{s.length} \le \texttt{500}1≤s.length≤500s \texttt{s}s由小写英语字母组成解法思路和算法为了确保相同字母最多出现在一个片段中需要使用哈希表记录每个字母在字符串s ss中最后一次出现的下标。对于下标i ii处的字母c cc将c cc最后一次出现的下标记为lastIndex \textit{lastIndex}lastIndex则包含下标i ii的片段的结束下标一定大于等于lastIndex \textit{lastIndex}lastIndex否则字母c cc会出现在多个片段中。在满足该条件的情况下为了划分出尽可能多的片段应使每个片段尽可能短每个片段的结束下标尽可能小。这是一个贪心的策略。得到每个字母在字符串s ss中最后一次出现的下标从左到右遍历字符串s ss遍历过程中维护当前片段的开始下标start \textit{start}start和结束下标end \textit{end}end。对于每个下标i ii执行如下操作。记c s [ i ] c s[i]cs[i]得到字母c cc的最后一次出现的下标lastIndex \textit{lastIndex}lastIndex则当前片段的结束下标一定大于等于lastIndex \textit{lastIndex}lastIndex因此将end \textit{end}end更新为max ⁡ ( end , lastIndex ) \max(\textit{end}, \textit{lastIndex})max(end,lastIndex)。如果i end i \textit{end}iend则当前下标i ii为当前片段的结束下标当前片段的下标范围是[ start , end ] [\textit{start}, \textit{end}][start,end]当前片段的长度是end − start 1 \textit{end} - \textit{start} 1end−start1将当前片段的长度添加到结果列表中然后将start \textit{start}start和end \textit{end}end都更新为i 1 i 1i1表示当前片段遍历结束如果有下一个字母则下标i 1 i 1i1为下一个片段的开始下标。遍历结束之后结果列表包含划分出的所有片段的长度。上述贪心策略的正确性说明如下。对于遍历到的每个字母都将当前片段的下标范围扩展到包含当前字母的最后一次出现的下标因此每个片段不可能更短否则当前字母会出现在多个片段中。遍历过程中遇到i end i \textit{end}iend时使用贪心策略将i ii作为当前片段的结束下标当i ii尚未到达字符串末尾时将下标i 1 i 1i1作为下一个片段的开始。如果不使用贪心策略则不将下标i ii作为当前片段的结束下标下一个片段的开始下标一定大于i 1 i 1i1字符串剩余部分的长度更少因此不使用贪心策略可以划分出的片段数量不可能超过使用贪心策略可以划分出的片段数量。代码classSolution{publicListIntegerpartitionLabels(Strings){int[]lastIndicesnewint[26];Arrays.fill(lastIndices,-1);intlengths.length();for(inti0;ilength;i){charcs.charAt(i);intindexc-a;lastIndices[index]i;}ListIntegerpartitionnewArrayListInteger();intstart0,end0;for(inti0;ilength;i){charcs.charAt(i);endMath.max(end,lastIndices[c-a]);if(iend){partition.add(end-start1);starti1;endi1;}}returnpartition;}}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是字符串s ss的长度。需要遍历字符串一次记录每个字母在字符串中最后一次出现的下标然后需要遍历字符串一次计算划分结果。空间复杂度O ( ∣ Σ ∣ ) O(|\Sigma|)O(∣Σ∣)其中Σ \SigmaΣ是字符集这道题中Σ \SigmaΣ是全部小写英语字母∣ Σ ∣ 26 |\Sigma| 26∣Σ∣26。空间复杂度主要取决于哈希表需要使用哈希表记录每个字母在字符串中最后一次出现的下标。注意返回值不计入空间复杂度。