763.划分字母区间

张开发
• 2026/4/16 2:59:29 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

763.划分字母区间
题目描述题解(贪心算法)思路代码classSolution{publicListIntegerpartitionLabels(Strings){// 用于记录每个小写字母最后一次出现的索引位置int[]lastnewint[26];intlengths.length();// 第一次遍历记录每个字母最后出现的下标for(inti0;ilength;i){last[s.charAt(i)-a]i;}ListIntegerpartitionnewArrayList();intstart0;// 当前片段的起始位置intend0;// 当前片段的结束位置// 第二次遍历利用贪心思想划分区间for(inti0;ilength;i){// 更新当前片段必须包含的最远位置endMath.max(end,last[s.charAt(i)-a]);// 如果当前索引走到了当前片段的最远位置说明可以安全地切分了if(iend){partition.add(end-start1);// 更新下一个片段的起始位置startend1;}}returnpartition;}}复杂度分析时间复杂度O(N)O(N)O(N)其中NNN是字符串的长度。我们需要遍历两次字符串第一次记录最后出现位置第二次进行区间划分。对常数大小的字母表26个的访问时间是O(1)O(1)O(1)整体是线性时间复杂度空间复杂度O(∣Σ∣)O(|\Sigma|)O(∣Σ∣)其中Σ\SigmaΣ是字符集。题目中说明字符串只包含小写英文字母因此我们需要一个大小为 26 的数组来记录字母的最后出现位置空间复杂度为O(1)O(1)O(1)即O(26)O(26)O(26)常数级别。返回值不计入空间复杂度

更多文章