題目描述:給定一個字串陣列 words 和一個整數 maxWidth,將文字排列成每行恰好 maxWidth 個字符的格式,並回傳所有行的字串列表。排版規則如下:
maxWidth。解題思路:整體策略是貪婪地打包每一行,再根據規則填充空格,是一道純粹的模擬題。
第一步:貪婪決定每行的單詞範圍
維護指標 i,每次從 i 開始盡可能多地將單詞加入當前行(計算加入後的最小寬度:所有單詞字符數加上單詞間至少一個空格),直到再加一個單詞就會超過 maxWidth 為止。
第二步:填充空格
totalChars。totalSpaces = maxWidth - totalChars。gaps = 單詞數 - 1;evenSpaces = totalSpaces / gaps;extraSpaces = totalSpaces % gaps(前 extraSpaces 個間隔各多一個空格)。第三步:拼接字串
按照計算好的間隔數,依序拼接單詞與空格,組成長度恰好為 maxWidth 的行。
時間複雜度:O(n × L) — n 為單詞數,L 為 maxWidth。外層迴圈每次推進至少一個單詞,總計處理 n 個單詞;每行的空格填充與字串拼接最多花費 O(L) 時間。整體為 O(n × L),實際上更接近 O(總字符數 + 總行數 × L)。
空間複雜度:O(n × L) — 輸出結果共有 O(n) 行,每行長度為 O(L),輸出本身佔 O(n × L) 空間。不計輸出的話,額外使用的變數為 O(1)。
1. Initialize result = [], i = 0
2. While i < n:
a. Start a new line with words[i]; set j = i + 1
b. While j < n and adding words[j] (with one space) fits in maxWidth:
- Extend line; j++
c. words[i..j-1] belong to this line; compute totalChars = sum of their lengths
d. If this is the last line OR only one word on line:
- Join words with single spaces, pad right with spaces to maxWidth
e. Else (full-justify):
- totalSpaces = maxWidth - totalChars
- evenSpaces = totalSpaces / (numWords - 1)
- extraSpaces = totalSpaces % (numWords - 1)
- For each gap k (0-indexed): use evenSpaces + (1 if k < extraSpaces else 0) spaces
- Concatenate words and computed spaces
f. Append line to result; set i = j
3. Return result方法一:預先分組再格式化(兩階段)
第一階段:遍歷 words,將每行應包含的單詞索引範圍存入一個列表(例如 vector<pair<int,int>>)。第二階段:對每個範圍獨立計算空格分配並拼接字串。邏輯上與一階段方法等價,但分離「分組」與「格式化」兩個關注點,程式碼結構更清晰,便於單獨測試每個階段。時間複雜度與空間複雜度相同,均為 O(n × L)。
方法二:字串流(stringstream)輔助
在拼接行字串時使用 C++ 的 ostringstream 或 Python 的 str.join,以更語義化的方式組合單詞和空格,避免手動管理索引計算時的 off-by-one 錯誤。本質上仍是相同的貪婪模擬,但借助語言內建工具減少實作細節的複雜度。時間複雜度 O(n × L),空間複雜度 O(n × L)。
"beautiful" 拆成 "beau-" 和 "tiful",排版演算法應如何擴展?這與 TeX 的斷行演算法(Knuth-Plass)有何關聯?words 陣列非常龐大(例如一篇完整文章),無法一次載入記憶體,如何設計一個串流(streaming)版本的排版器,邊讀入單詞邊輸出已完成的行?