LeetCode 68. 文本左右对齐 题解（贪心算法）
一、题目描述
给定一个单词数words 和一个最大行宽度 maxWidth，需要重新排版文本，满足以下严格规则：
核心要求
-
贪心放置：每行尽可能多的放入单词，不浪费空间；
-
行宽度固定：每行字符总数必须严格等于
maxWidth，不足用空格补齐； -
空格均匀分配：非最后一行、且多个单词时，单词间空格尽量均匀；无法均分则**左侧空格多于右侧**；
-
最后一行特殊规则：最后一行强制**左对齐**，单词间仅保留单个空格，行末统一补空格至最大宽度；
-
单个单词的行：直接左对齐，右侧补满空格。
二、解题核心思路
本题标准解法为 贪心算法，整体分为两大阶段：**贪心取行单词** + 按规则拼接行字符串。
1. 贪心选取每行单词
遍历单词数组，逐行装填单词。装填规则：
新加入一个单词的总占用长度 = 当前已选单词总长度 + 新单词长度 + 已有单词个数（最少间隔空格数）
原理m 个单词至少需要 m-1 个空格间隔，每新增一个单词，默认多1个间隔空格。
如果新增单词后总长度不超过 maxWidth，则放入当前行，否则终止当前行装填，开始格式化本行。
2. 分行格式化规则（核心难点）
将行分为两种情况处理，完全贴合题目要求：
-
情况一：最后一行 / 行内只有一个单词：左对齐，单词间单个空格，行末尾补空格至最大宽度；
-
情况二：普通行（非最后一行、多个单词）：两端对齐，均匀分配空格，多余空格优先分给左侧间隔。
三、完整AC代码（C++）
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> ans;
int i = 0;
int n = words.size();
while(i < n){
// 贪心搜集当前行可以放置的所有单词
vector<string> line;
int len = 0;
// line.size() 代表当前最少需要的空格数
while(i<n && len + words[i].size()+(int)line.size() <= maxWidth){
line.push\_back(words[i]);
len+=words[i].size();
i++;
}
// 判断是否是最后一行
bool lastline = (i == n);
string row;
// 最后一行 或 单行只有一个单词：左对齐处理
if(lastline || line.size() == 1){
row = line[0];
for(int k = 1;k < line.size();k++){
row+=' '+line[k];
}
// 末尾补空格至maxWidth
row += string(maxWidth - row.size(), ' ');
}else{
// 普通行：两端对齐，均匀分配空格
int total = maxWidth - len; // 需要填充的总空格数
int solt = line.size() - 1; // 单词间隔数量
int sp = total / solt; // 每个间隔基础空格数
int are = total % solt; // 需要多分配1个空格的左侧间隔数量
// 遍历拼接所有单词和空格
for(int k = 0;k < line.size() - 1;k++){
row+= line[k];
// 前are个间隔，多补1个空格
int space = sp + (k < are?1:0);
row+=string(space,' ');
}
// 拼接最后一个单词
row+=line.back();
}
ans.push\_back(row);
}
return ans;
}
};
四、代码逐行深度解析
1. 初始化变量
ans：存储最终排版完成的所有行结果；
i：全局遍历单词的指针，永不回头，符合贪心思想；
n：单词数组总个数。
2. 贪心搜集当前行单词
line 临时存储当前行的所有单词len 统计当前行所有单词的**纯字符总长度（不含空格）**。
判断条件 len + words[i].size() + line.size() <= maxWidth：
新增单词长度 + 已有单词总长 + 最少间隔空格数（当前单词数），不超最大宽度则放入本行。
3. 分行判断逻辑
lastline = (i == n)：指针走到末尾，说明当前行为最后一行。
4. 左对齐分支（最后一行 / 单个单词）
先以单个空格拼接所有单词，保证正常语句格式，最后在字符串**末尾统一补空格**填满整行宽度，严格符合最后一行左对齐规则。
5. 两端对齐分支（核心算法）
-
total：当前行需要填充的**总空格数量**（总宽度 - 单词纯长度）； -
solt：单词之间的间隔总数，等于单词数-1； -
sp：每个间隔的**基础空格数**； -
are：多余出来无法均分的空格数量，**前are个间隔各多补1个空格**，满足「左多右少」的题目要求。
循环拼接前 line.size()-1 个单词，按需补空格，最后拼接末尾单词，完成整行构造。
五、复杂度分析
时间复杂度：O(N)
N 为所有单词的字符总数。每个单词、每个空格仅被拼接一次，无重复遍历，线性时间复杂度。
空间复杂度：O(N)
临时存储每行单词的数组、结果集均为线性空间，仅用于存储结果，无额外冗余空间。