給你一個(gè)字符串?s?。我們要把這個(gè)字符串劃分為盡可能多的片段，同一字母最多出現(xiàn)在一個(gè)片段中。

注意，劃分結(jié)果需要滿足：將所有劃分結(jié)果按順序連接，得到的字符串仍然是?s?。

返回一個(gè)表示每個(gè)字符串片段的長度的列表。

思路 貪心算法

數(shù)組 last 存儲(chǔ)每個(gè)字母最后出現(xiàn)的下標(biāo)

利用滑動(dòng)窗口，每次更新end指針，如果最后出現(xiàn)的下標(biāo) i == end，說明找到當(dāng)前最大片段，則加入結(jié)果中，更新?start指針

public class Solution {public IList<int> PartitionLabels(string s) {int[] last = new int[26];for(int i = 0; i < s.Length; i++){last[s[i] - 'a'] = i;}List<int> result = new List<int>();int start = 0, end = 0;for(int i = 0; i < s.Length; i++){end = Math.Max(end, last[s[i] - 'a']);if(i == end){result.Add(end - start + 1);start = end + 1;}}return result;}
}

復(fù)雜度分析?

• 時(shí)間復(fù)雜度：O(n)，其中?n?是字符串?s?的長度。需要遍歷字符串一次記錄每個(gè)字母在字符串中最后一次出現(xiàn)的下標(biāo)，然后需要遍歷字符串一次計(jì)算劃分結(jié)果。

• 空間復(fù)雜度：O(∣Σ∣)，其中 Σ 是字符集，這道題中 Σ 是全部小寫英語字母，∣Σ∣=26?？臻g復(fù)雜度主要取決于哈希表，需要使用哈希表記錄每個(gè)字母在字符串中最后一次出現(xiàn)的下標(biāo)。注意返回值不計(jì)入空間復(fù)雜度。