京公网安备11010502063487号给定一组单词和一个行宽，把单词排成若干行，每行恰好 maxWidth 个字符，要求：每行尽量多放单词（贪心）；单词之间至少一个空格；中间的行两端对齐，多余的空格尽量平均地分到单词之间的空隙里，如果分不均匀，左边的空隙多一个；最后一行左对齐，单词之间只有一个空格，右边补空格；只有一个单词的行也是左对齐。这道题没有算法难度，全是细节，最容易错的是空格怎么分。本文用真实运行对比"多出来的空格放左边还是放右边"，用 20000 组随机数据验证输出满足的几个基本性质，给出五种语言的实现，并把逐行排版做成分步演示。
完整题目见官方页面（链接在文末）。每个单词的长度不超过行宽。基准解用另一种方式排空格：先给每个空隙放 1 个，再把剩下的空格一个一个地轮流放进从左到右的各个空隙，直到用完；而 solve 用整除和取余一次算出每个空隙的空格数，两者是不同的算法。一共 12 组用例，覆盖：官方三个示例、只有一个单词的行、每行只能放一个单词、空格分不均匀：
输入 [["This","is","an","example","of","text","justification."],16] 输出 ["This is an","example of text","justification. "] 输入 [["What","must","be","acknowledgment","shall","be"],16] 输出 ["What must be","acknowledgment ","shall be "] 输入 [["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"],20] 输出 ["Science is what we","understand well","enough to explain to","a computer. Art is","everything else we","do "] 输入 [["a"],1] 输出 ["a"] 输入 [["a"],5] 输出 ["a "] 输入 [["a","b","c"],4] 输出 ["a b","c "]
平均分配空格时，如果分不均匀，规则是"左边的空隙比右边的多"。下面对官方第一个示例（行宽 16）对比了两种放法：
多出来的空格放在最后几个空隙（错误）vs 前几个空隙（正确），行宽 16： 错误 |This is an| 错误 |example of text| 错误 |justification. | 正确 |This is an| 正确 |example of text| 正确 |justification. |
第二行 example of text 中间有 3 个空格要分到 2 个空隙里，每个空隙至少 1 个，多出的 1 个应该放在左边的空隙：example of text；如果错误地放在右边就是 example of text。同一个示例里的第一行（8 个空格分到 2 个空隙，正好各 4 个）和最后一行（左对齐）两种放法相同，所以这个错误只在空格分不均匀的行里才出现。
外层循环一次处理一行：从第 i 个单词开始，尽量往后放单词，条件是"已放的字母数 + 这个单词的长度 + 已放单词之间的最少空格数（单词个数减一）不超过行宽"，得到这一行的单词是 [i, j)。然后分情况：如果 j 到了末尾（最后一行），或者这一行只有一个单词（没有空隙），左对齐——单词之间用一个空格连接，右边补空格到行宽；否则总空格数是行宽减去字母数，除以空隙数得到每个空隙的基础空格数 q 和余数 r，前 r 个空隙多放一个空格。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(words, max_width): res = [] i, n = 0, len(words) while i < n: j, length = i, 0 while j < n and length + len(words[j]) + (j - i) <= max_width: # 贪心：这一行尽量多塞单词（单词之间至少 1 个空格） length += len(words[j]) j += 1 line_words = words[i:j] gaps = j - i - 1 # 单词之间的空隙数 if j == n or gaps == 0: # 最后一行，或者这一行只有一个单词：左对齐，右边补空格 line = " ".join(line_words) line += " " * (max_width - len(line)) else: # 其他行：两端对齐，空格尽量平均分配 spaces = max_width - length q, r = divmod(spaces, gaps) # 每个空隙至少 q 个空格，前 r 个空隙多一个 line = "" for k in range(gaps): line += line_words[k] + " " * (q + (1 if k < r else 0)) line += line_words[-1] res.append(line) i = j return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [["This","is","an","example","of","text","justification."],16] → ["This is an","example of text","justification. "] [["What","must","be","acknowledgment","shall","be"],16] → ["What must be","acknowledgment ","shall be "] [["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"],20] → ["Science is what we","understand well","enough to explain to","a computer. Art is","everything else we","do "] [["a"],1] → ["a"] [["a"],5] → ["a "] [["a","b","c"],4] → ["a b","c "]
Java · 解法代码class Solution { public List<String> fullJustify(String[] words, int maxWidth) { List<String> res = new ArrayList<>(); int i = 0, n = words.length; while (i < n) { int j = i, length = 0; while (j < n && length + words[j].length() + (j - i) <= maxWidth) { // 贪心：这一行尽量多塞单词 length += words[j].length(); j++; } int gaps = j - i - 1; // 单词之间的空隙数 StringBuilder sb = new StringBuilder(); if (j == n || gaps == 0) { // 最后一行，或者只有一个单词：左对齐，右边补空格 for (int k = i; k < j; k++) { sb.append(words[k]); if (k < j - 1) sb.append(' '); } while (sb.length() < maxWidth) sb.append(' '); } else { // 其他行：两端对齐，空格尽量平均分配 int spaces = maxWidth - length; int q = spaces / gaps, r = spaces % gaps; // 每个空隙至少 q 个空格，前 r 个空隙多一个 for (int k = 0; k < gaps; k++) { sb.append(words[i + k]); for (int s = 0; s < q + (k < r ? 1 : 0); s++) sb.append(' '); } sb.append(words[j - 1]); } res.add(sb.toString()); i = j; } return res; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [["This","is","an","example","of","text","justification."],16] → ["This is an","example of text","justification. "] [["What","must","be","acknowledgment","shall","be"],16] → ["What must be","acknowledgment ","shall be "] [["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"],20] → ["Science is what we","understand well","enough to explain to","a computer. Art is","everything else we","do "] [["a"],1] → ["a"] [["a"],5] → ["a "] [["a","b","c"],4] → ["a b","c "]
Go · 解法代码func fullJustify(words []string, maxWidth int) []string { res := []string{} i, n := 0, len(words) for i < n { j, length := i, 0 for j < n && length+len(words[j])+(j-i) <= maxWidth { // 贪心：这一行尽量多塞单词 length += len(words[j]) j++ } gaps := j - i - 1 // 单词之间的空隙数 var sb strings.Builder if j == n || gaps == 0 { // 最后一行，或者只有一个单词：左对齐，右边补空格 line := strings.Join(words[i:j], " ") sb.WriteString(line) sb.WriteString(strings.Repeat(" ", maxWidth-len(line))) } else { // 其他行：两端对齐，空格尽量平均分配 spaces := maxWidth - length q, r := spaces/gaps, spaces%gaps // 每个空隙至少 q 个空格，前 r 个空隙多一个 for k := 0; k < gaps; k++ { sb.WriteString(words[i+k]) extra := q if k < r { extra++ } sb.WriteString(strings.Repeat(" ", extra)) } sb.WriteString(words[j-1]) } res = append(res, sb.String()) i = j } return res }
$ go build -o bin . && ./bin < cases.jsonl [["This","is","an","example","of","text","justification."],16] → ["This is an","example of text","justification. "] [["What","must","be","acknowledgment","shall","be"],16] → ["What must be","acknowledgment ","shall be "] [["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"],20] → ["Science is what we","understand well","enough to explain to","a computer. Art is","everything else we","do "] [["a"],1] → ["a"] [["a"],5] → ["a "] [["a","b","c"],4] → ["a b","c "]
JavaScript · 解法代码function fullJustify(words, maxWidth) { const res = []; let i = 0; const n = words.length; while (i < n) { let j = i, length = 0; while (j < n && length + words[j].length + (j - i) <= maxWidth) { // 贪心：这一行尽量多塞单词 length += words[j].length; j++; } const gaps = j - i - 1; // 单词之间的空隙数 let line; if (j === n || gaps === 0) { // 最后一行，或者只有一个单词：左对齐，右边补空格 line = words.slice(i, j).join(" "); line += " ".repeat(maxWidth - line.length); } else { // 其他行：两端对齐，空格尽量平均分配 const spaces = maxWidth - length; const q = Math.floor(spaces / gaps), r = spaces % gaps; // 每个空隙至少 q 个空格，前 r 个空隙多一个 line = ""; for (let k = 0; k < gaps; k++) line += words[i + k] + " ".repeat(q + (k < r ? 1 : 0)); line += words[j - 1]; } res.push(line); i = j; } return res; }
$ node run.js < cases.jsonl [["This","is","an","example","of","text","justification."],16] → ["This is an","example of text","justification. "] [["What","must","be","acknowledgment","shall","be"],16] → ["What must be","acknowledgment ","shall be "] [["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"],20] → ["Science is what we","understand well","enough to explain to","a computer. Art is","everything else we","do "] [["a"],1] → ["a"] [["a"],5] → ["a "] [["a","b","c"],4] → ["a b","c "]
C++ · 解法代码#include <string> #include <vector> using namespace std; class Solution { public: vector<string> fullJustify(vector<string>& words, int maxWidth) { vector<string> res; int i = 0, n = words.size(); while (i < n) { int j = i, length = 0; while (j < n && length + (int)words[j].size() + (j - i) <= maxWidth) { // 贪心：这一行尽量多塞单词 length += words[j].size(); j++; } int gaps = j - i - 1; // 单词之间的空隙数 string line; if (j == n || gaps == 0) { // 最后一行，或者只有一个单词：左对齐，右边补空格 for (int k = i; k < j; k++) { line += words[k]; if (k < j - 1) line += ' '; } line += string(maxWidth - line.size(), ' '); } else { // 其他行：两端对齐，空格尽量平均分配 int spaces = maxWidth - length; int q = spaces / gaps, r = spaces % gaps; // 每个空隙至少 q 个空格，前 r 个空隙多一个 for (int k = 0; k < gaps; k++) line += words[i + k] + string(q + (k < r ? 1 : 0), ' '); line += words[j - 1]; } res.push_back(line); i = j; } return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [["This","is","an","example","of","text","justification."],16] → ["This is an","example of text","justification. "] [["What","must","be","acknowledgment","shall","be"],16] → ["What must be","acknowledgment ","shall be "] [["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"],20] → ["Science is what we","understand well","enough to explain to","a computer. Art is","everything else we","do "] [["a"],1] → ["a"] [["a"],5] → ["a "] [["a","b","c"],4] → ["a b","c "]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
因为这道题的输出是一段格式化文本，我除了和基准解逐行对比，还对 20000 组随机数据检查了 solve 输出必须满足的几个性质，这些检查不依赖任何基准解：
用 20000 组随机数据检查 solve 输出的性质（不依赖基准解）： 每行宽度都恰好等于行宽：违反 0 组 把所有行里的单词依次连起来等于原单词序列：违反 0 组 每一行都已经尽可能多地放了单词（放不下下一行的第一个单词）：违反 0 组 最后一行是左对齐、单词之间只有一个空格：违反 0 组
20000 组数据里，每一行的宽度都恰好等于行宽；把所有行里的单词依次连起来正好等于原来的单词序列（没有丢词、重复或乱序）；除最后一行外，每一行都已经尽可能多地放了单词（放不下下一行的第一个单词）；最后一行是左对齐、单词之间只有一个空格。四条性质都没有任何一组违反。
Python 版本另外和基准解做了随机对拍：1 到 9 个长 1 到 6 的单词，行宽取最长单词到 14：
随机对拍 20000 组（1 到 9 个长 1 到 6 的单词，行宽取「最长单词」到 14），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。这道题每个单词只处理常数次，是线性的，所以没有做规模对比实验。
下面的演示用官方第一个示例，行宽 16。第一行 This is an 字母共 8 个，需要 8 个空格分到 2 个空隙，每个 4 个；第二行 example of text 字母共 13 个，需要 3 个空格分到 2 个空隙，每个 1 个，前 1 个空隙再多 1 个；第三行是最后一行 justification.，左对齐，右边补 2 个空格。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。