题目描述
![]()
题解(贪心算法)
思路
![]()
代码
classSolution{publicList<Integer>partitionLabels(Strings){// 用于记录每个小写字母最后一次出现的索引位置int[]last=newint[26];intlength=s.length();// 第一次遍历：记录每个字母最后出现的下标for(inti=0;i<length;i++){last[s.charAt(i)-'a']=i;}List<Integer>partition=newArrayList<>();intstart=0;// 当前片段的起始位置intend=0;// 当前片段的结束位置// 第二次遍历：利用贪心思想划分区间for(inti=0;i<length;i++){// 更新当前片段必须包含的最远位置end=Math.max(end,last[s.charAt(i)-'a']);// 如果当前索引走到了当前片段的最远位置，说明可以安全地切分了if(i==end){partition.add(end-start+1);// 更新下一个片段的起始位置start=end+1;}}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)常数级别）。返回值不计入空间复杂度
