doocs/leetcode 精讲：LeetCode 68. 文本左右对齐（Text Justification）——贪心取词与空格均匀分配的模拟解法全解析

• 示例工程

本文以 68. 文本左右对齐 题解文档为主线，完整拆解这道"困难"标签下实为「贪心 + 模拟」的经典题目：如何用贪心策略尽可能多地往每行塞入单词，如何让多余空格在词间"尽量均匀、左侧偏多"地分配，以及最后一行/单单词行必须左对齐的特殊规则。读完本文，你将掌握一套可直接运行的六语言实现（Python/Java/C++/Go/TypeScript/C#），并能独立推导出任意输入下的逐行输出。

一、题目概述：给出一份"两端对齐"的文本

给定一个单词数组words和一个行宽maxWidth，要求重新排版单词，使得每一行恰好有maxWidth个字符，并且左右两端对齐（fully justified）。这是文字处理软件中常见的"两端对齐"排版需求，本题要求你用算法把这一排版过程精确复现出来。

题目要求使用贪心算法放置单词：尽可能多地往每行中放置单词，必要时用空格' '填充，使每行恰好达到maxWidth个字符。其核心排版规则可以归纳为三条：

1. 贪心取词：从左到右扫描，每行尽量多装单词，装不下就换行；
2. 均匀分配：词间空格要尽可能均匀；若无法整除，则左侧间隙多放空格（即左侧空格数 ≥ 右侧空格数）；
3. 末行左对齐：文本的最后一行应为左对齐，单词之间只保留 1 个空格，剩余宽度全部补在行尾；同理，一行只有一个单词时也按左对齐处理。

题目还给出三条注意项：单词是由非空格字符组成的字符序列；每个单词长度大于 0 且不超过maxWidth；输入单词数组至少包含一个单词。

数据约束

数据规模很小，复杂度不是瓶颈；真正的难点在于空格分配的各种边界细节。

二、示例逐行推演：把规则落到输出上

示例 1：普通行的均匀分配

输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 输出: [ "This is an", "example of text", "justification. " ]

逐行验证（.表示一个空格）：

• 第 1 行取This is an：字符总长4+2+2=10，两处词间基础空格共 2 个，还差16-12=4个空格需要补进 2 个间隙 → 每个间隙再补 2 个 → 词间各 3 个空格：This...is...an（4+4+2+4+2=16）。
• 第 2 行取example of text：字符总长7+2+4=13，基础空格 2 个，共 15，还差 1 个空格补进 2 个间隙 → 按"左多右少"规则，左侧间隙 +1：example..of.text（7+3+2+2+4=16）。
• 第 3 行只有justification.（14 个字符）→ 左对齐，行尾补2个空格。

示例 2：末行左对齐 + 单单词行

输入: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16 输出: [ "What must be", "acknowledgment ", "shall be " ]

• 第 1 行What must be：字符总长4+4+2=10，基础空格 2，共 12，还差 4 个空格 → 2 个间隙各补 2 个 → 词间各 3 个空格：What...must...be。
• 第 2 行只有acknowledgment（14 字符）→ 左对齐，行尾补 2 个空格。题目解释明确指出：第二行同样为左对齐，因为这一行只包含一个单词。
• 第 3 行是最后一行 → 必须左对齐：shall be（8 字符）只保留 1 个空格，行尾补16-8=8个空格，即"shall be "，而不是"shall be"。

示例 3：更多行的综合推演

输入: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20 输出: [ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do " ]

其中第 4 行a computer. Art is字符总长1+9+3+2=15，基础空格 3，共 18，还差 2 个空格补进 3 个间隙 →w=0, m=2，前 2 个间隙各 +1 → 词间空格依次为 2、2、1：a..computer...Art.is。第 6 行是末行，do（2 字符）左对齐后行尾补 18 个空格。

提示：题目文档示例中的多个连续空格在 HTML 渲染时会被折叠，阅读原始输出时需结合空格实体（ ）或上述数学推演理解真实字符数。

三、解题思路：贪心取词 + 模拟排版

这道题的算法骨架并不复杂：从左到右扫描单词，每轮先贪心地取出一行能放下的所有单词，再根据该行性质决定排版方式。整个过程不需要回溯，因为每一行的内容只由"当前剩余单词 + maxWidth"决定，行与行之间不存在需要回头调整的依赖关系。

步骤拆解

1. 贪心取词：以当前指针i为行首，先把words[i]放入本行；然后持续尝试加入下一个单词，前提是已占用字符数 cnt + 1 + 下一个单词长度 <= maxWidth（1代表词间必须保留的基础空格）。
2. 判断排版方式：
   • 若i == n（当前行是最后一行）或len(t) == 1（本行只有一个单词）→左对齐：单词间以 1 个空格连接，行尾用空格补齐到maxWidth；
   • 否则 →均匀分配：把多余空格尽量均匀地填进词间空隙，余数优先给左侧。
3. 循环直到所有单词处理完毕，逐行加入答案数组。

均匀分配公式推导

设本行单词数为k = len(t)，累计计数cnt的语义是：所有单词字符长度之和 + (k-1) 个基础空格。因此：

• 纯字符总长 =cnt - (k - 1)；
• 需要在词间额外分配的空格总数space_width = maxWidth - (cnt - k + 1)（即maxWidth - 纯字符总长 - (k-1) 个基础空格）；
• 每个间隙的基础额外空格w = space_width // (k - 1)，余数m = space_width % (k - 1)；
• 前m个间隙各多放 1 个空格，从而天然满足"左侧间隙空格数 ≥ 右侧"的要求。

当space_width恰好能被k-1整除时（m == 0），所有间隙完全均匀，例如示例 1 第 1 行与示例 3 第 2 行。

复杂度分析

设L为所有单词的长度之和：

• 时间复杂度O(L)：每个单词恰好被扫描、加入、输出一次；
• 空间复杂度O(L)：答案数组与单行临时容器累计占用与总字符量同阶。

原题解文档明确指出：单词数不超过 300、行宽不超过 100，从左到右贪心取词即可，不必回溯。

四、源码逐段解析（以 Python3 为主线）

仓库 Solution.py 与题解文档中的 Python3 实现完全一致，下面逐段拆解：

class Solution: def fullJustify(self, words: List[str], maxWidth: int) -> List[str]: ans = [] i, n = 0, len(words) while i < n: # —— 阶段一：贪心取词，确定本行单词 t —— t = [] cnt = len(words[i]) t.append(words[i]) i += 1 while i < n and cnt + 1 + len(words[i]) <= maxWidth: cnt += 1 + len(words[i]) t.append(words[i]) i += 1 # —— 阶段二：左对齐分支（末行或单单词行）—— if i == n or len(t) == 1: left = ' '.join(t) right = ' ' * (maxWidth - len(left)) ans.append(left + right) continue # —— 阶段三：均匀分配分支 —— space_width = maxWidth - (cnt - len(t) + 1) w, m = divmod(space_width, len(t) - 1) row = [] for j, s in enumerate(t[:-1]): row.append(s) row.append(' ' * (w + (1 if j < m else 0))) row.append(t[-1]) ans.append(''.join(row)) return ans

三个关键细节：

• cnt的累积策略：cnt + 1 + len(words[i])中的+1表示新单词与上一单词之间的基础空格，这保证cnt始终等于"本行已取单词字符长度 + 词间基础空格数"；
• divmod(space_width, len(t) - 1)：一次得到基础额外空格w与余数m；j < m的间隙多放 1 个空格，实现"左侧优先"；
• row.append(t[-1])：最后一个单词之后不再追加空格，行宽恰好由前面分配的间隙填满。

五、多语言实现对照

原题解文档提供了六种语言的同构实现（方法名均为fullJustify），仓库中也存在对应的独立源码文件：Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.cs。算法骨架完全相同，仅语法层面有差异：

以 Java 为例的完整实现：

class Solution { public List<String> fullJustify(String[] words, int maxWidth) { List<String> ans = new ArrayList<>(); for (int i = 0, n = words.length; i < n;) { List<String> t = new ArrayList<>(); t.add(words[i]); int cnt = words[i].length(); ++i; while (i < n && cnt + 1 + words[i].length() <= maxWidth) { cnt += 1 + words[i].length(); t.add(words[i++]); } if (i == n || t.size() == 1) { String left = String.join(" ", t); String right = " ".repeat(maxWidth - left.length()); ans.add(left + right); continue; } int spaceWidth = maxWidth - (cnt - t.size() + 1); int w = spaceWidth / (t.size() - 1); int m = spaceWidth % (t.size() - 1); StringBuilder row = new StringBuilder(); for (int j = 0; j < t.size() - 1; ++j) { row.append(t.get(j)); row.append(" ".repeat(w + (j < m ? 1 : 0))); } row.append(t.get(t.size() - 1)); ans.add(row.toString()); } return ans; } }

C++ 实现中值得注意的写法：左对齐时用string(maxWidth - left.size(), ' ')一次性构造填充空格；均匀分配时用row += t[j] + string(w + (j < m ? 1 : 0), ' ')将"单词 + 空格"一并拼入：

class Solution { public: vector<string> fullJustify(vector<string>& words, int maxWidth) { vector<string> ans; for (int i = 0, n = words.size(); i < n;) { vector<string> t = {words[i]}; int cnt = words[i].size(); ++i; while (i < n && cnt + 1 + words[i].size() <= maxWidth) { cnt += 1 + words[i].size(); t.emplace_back(words[i++]); } if (i == n || t.size() == 1) { string left = t[0]; for (int j = 1; j < t.size(); ++j) { left += " " + t[j]; } string right = string(maxWidth - left.size(), ' '); ans.emplace_back(left + right); continue; } int spaceWidth = maxWidth - (cnt - t.size() + 1); int w = spaceWidth / (t.size() - 1); int m = spaceWidth % (t.size() - 1); string row; for (int j = 0; j < t.size() - 1; ++j) { row += t[j] + string(w + (j < m ? 1 : 0), ' '); } row += t.back(); ans.emplace_back(row); } return ans; } };

Go 与 TypeScript 的实现则分别利用了strings.Builder和数组join来避免频繁的字符串拼接开销，整体结构与其他语言一一对应。

六、边界情况与易错点总结

这类"困难"题目的失分点几乎全部集中在边界处理上，做题与 review 代码时建议逐条核对：

1. 末行判定：i == n意味着当前行是最后一行，必须左对齐——即使它包含多个单词，也不能做均匀分配，只能行尾补空格；
2. 单单词行：一行只有一个单词时，len(t) - 1 == 0，均匀分配公式会出现除零，因此必须单独走左对齐分支（示例 2 的第二行）；
3. 整除与余数：w = space_width / (k - 1)、m = space_width % (k - 1)要分开处理，余数m只影响前 m 个间隙；
4. 末行行尾空格：最后一行补齐的空格数 =maxWidth - 已排版字符数，一个都不能少（示例 2 第三行需补 8 个空格）；
5. 恰好放满：当一行单词（含基础空格）恰好等于maxWidth时，space_width = 0，此时所有间隙保持 1 个空格，例如示例 3 的第 3 行enough to explain to；
6. 单词等于行宽：由于words[i].length <= maxWidth，最坏情况是某个单词长度恰好等于maxWidth，此时它独占一行，行尾补 0 个空格。

七、仓库中的完整资源与延伸阅读

本题在仓库中的资源非常完整，除题解文档外还有独立的多语言源码文件，可直接在对应语言环境中运行验证：

• 中文题解：README.md
• 英文题解：README_EN.md
• 独立源码：Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.cs

题目本身位于 solution/0000-0099 目录区间，该区间收录了 200 道题目（编号 0000-0099）的中英文题解。同类"数组 + 字符串 + 模拟"标签的题目（如滑动窗口、双指针类模拟题）可以在该目录中交叉检索，加深对"规则复杂但实现直接"类题目的理解。

小结

LeetCode 68「文本左右对齐」是一道典型的"算法简单、规则繁琐"的模拟题：核心算法只有贪心取词 + 线性扫描，时间复杂度 O(L)，但空格分配必须同时满足"均匀"与"左侧偏多"两条约束，还要单独处理末行与单单词行的左对齐场景。掌握cnt计数、divmod求w/m、j < m左侧优先这三板斧，你就能在任何语言中快速复现这道题的完整解法。建议用示例 2、示例 3 的输入自测输出，重点核对行尾空格数，即可确认实现与题解完全一致。

• 示例工程