題目描述:給定一個字串 s,將其分割成盡可能多的區段,使得每個字母最多只出現在一個區段中。回傳一個整數陣列,表示每個區段的長度。
解題思路:使用貪心策略,分兩個步驟。
第一步:記錄每個字元在字串中最後出現的位置。建立一個大小為 26 的陣列 last,last[c] 表示字元 c 在字串中最後一次出現的索引。
第二步:用一個指標掃描字串,同時維護當前區段的起始位置 start 和當前區段必須延伸到的最遠位置 end。對於每個字元 s[i],將 end 更新為 max(end, last[s[i]]),表示為了讓 s[i] 只出現在此區段,區段至少要延伸到 last[s[i]]。
當 i == end 時,表示當前區段已包含了所有在其中出現字元的最後出現位置,可以在此切割。記錄區段長度 end - start + 1,然後將 start 更新為 i + 1,開始新的區段。
關鍵洞察:每個字元必須完整地待在某個區段內(即從第一次到最後一次出現都在同一區段)。貪心地盡量在最早可能的位置切割,確保每個區段盡量短,從而切割出盡量多的區段。
時間複雜度:O(n) — 第一次遍歷建立 last 陣列為 O(n);第二次遍歷進行切割也為 O(n),總共 O(n)。
空間複雜度:O(1) — last 陣列大小固定為 26(字母數量),不隨輸入大小增長;輸出陣列不計入額外空間。
1. Build last[26]: for each index i, set last[s[i] - 'a'] = i.
2. Initialize start = 0, end = 0, result = [].
3. For i from 0 to len(s) - 1:
a. Update end = max(end, last[s[i] - 'a']).
b. If i == end:
- Append (end - start + 1) to result.
- Set start = i + 1.
4. Return result.合併區間 O(n log n):先為每個字元計算其在字串中出現的範圍 [first, last],然後將所有 26 個範圍視為區間進行合併(如同 Merge Intervals 問題)。最終合併後的每個區間對應一個區段。此方法概念清晰但需要排序步驟,複雜度稍高。
滑動視窗 O(n):與主解法本質相同,但改用明確的視窗邊界概念描述:視窗右邊界動態擴展,當遍歷指標追上右邊界時收割視窗。實作細節一致,只是觀點不同。
last 陣列應如何替換為更通用的資料結構?last 陣列的情況下(即只用一次遍歷)解決此問題?若不行,請解釋原因。