LeetCode 68. 文本左右对齐
目录
题目描述
题意分析
给一个单词数组
words和一个整数maxWidth，把这些单词排版成若干行文本，每行的长度恰好等于maxWidth，返回这些行组成的列表。排版规则必须逐条抠清楚，这题的难度全在规则本身：
- 单词的先后顺序不能改变，只能顺序地切成一行一行。
- 每行要贪心地塞尽量多的单词：只要再加一个单词（连同它前面必须有的那一个空格）后总长仍不超过
maxWidth，就必须加进来。- 同一行相邻两个单词之间至少要有一个空格。
- 非最后一行采用两端对齐：把该行剩余的空格分配到单词之间的各个间隔里，要求尽量均匀；如果不能整除，左边的间隔要比右边的间隔多分一个空格。
- 最后一行采用左对齐：单词之间只放一个空格，剩下的空格全部补在行尾。
- 一行里只有一个单词时没有间隔可分，也按左对齐处理：单词顶格，其余全部补成行尾空格。
题目保证每个单词的长度都不超过
maxWidth，所以不存在「一个单词都放不下」的情况。这题的算法复杂度并不高，真正的考点是边界和格式细节：每行长度必须精确等于
maxWidth，多一个空格或少一个空格都算错。边界情况包括：某一行只有一个单词；最后一行；剩余空格不能被间隔数整除；单词刚好把一行填满使得间隔空格恰为最小值；以及整个输入只有一个单词，此时它既是第一行也是最后一行。
解法：逐行贪心分组并分配空格
核心思路
每一行分成两个阶段处理：先确定这一行能放哪些单词，再按规则分配空格。两件事分开，边界会清楚很多。
第一阶段：贪心装入尽可能多的单词。 假设本行从
\[\text{wordsLen} + \operatorname{len}(\text{words}[idx]) + (idx-left) \le \text{maxWidth}\]left开始，wordsLen是已选单词的字符总数，准备加入下标idx的单词。加入后至少需要idx - left个间隔，因此可放入的条件是：若连最少的一个空格都放不下，当前行就必须结束；继续留空并不能让后面的单词提前，所以贪心取最多单词是安全的。
第二阶段：格式化当前行。 设单词区间为
[left, right)，单词总长为wordsLen，则待分配空格数为spaces = maxWidth - wordsLen，间隔数为gaps = right - left - 1：
- 最后一行或只有一个单词：单词之间放一个空格，其余补到行尾，保持左对齐；
- 普通行：每个间隔先放
spaces / gaps个空格，再把余下的spaces % gaps个空格依次补给最左边的间隔。这样始终满足三个不变量：单词顺序不变、每行长度恰好为
maxWidth、普通行左侧间隔的空格数不会少于右侧。
解题步骤
- 从
idx指向的单词开始，累加单词长度；把必要的最少间隔也算入，直到下一个单词放不下。- 记录本行区间
[left, idx)、单词总长度wordsLen，判断它是否为最后一行。- 若是最后一行或只有一个单词，使用单空格连接，再在末尾补空格。
- 否则计算
spaces、gaps、平均空格数base和余数extra。- 从左到右拼接：前
extra个间隔放base + 1个空格，其余放base个。- 重复处理下一行，直到所有单词用完。
例如
maxWidth = 16，某普通行装入["Science","is","what"]：单词总长为 13，共有 3 个空格、2 个间隔，所以base = 1、extra = 1。左侧间隔多拿一个空格，得到"Science is what"，长度正好为 16。
代码实现
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> ans = new ArrayList<>();
int idx = 0;
while (idx < words.length) {
int left = idx;
int wordsLen = 0;
while (idx < words.length
&& wordsLen + words[idx].length() + idx - left <= maxWidth) {
wordsLen += words[idx].length();
idx++;
}
ans.add(buildLine(words, left, idx, wordsLen, maxWidth,
idx == words.length));
}
return ans;
}
private String buildLine(String[] words, int left, int right,
int wordsLen, int maxWidth, boolean lastLine) {
StringBuilder line = new StringBuilder(maxWidth);
int gaps = right - left - 1;
if (lastLine || gaps == 0) {
for (int i = left; i < right; i++) {
if (i > left) {
line.append(' ');
}
line.append(words[i]);
}
appendSpaces(line, maxWidth - line.length());
return line.toString();
}
int spaces = maxWidth - wordsLen;
int base = spaces / gaps;
int extra = spaces % gaps;
for (int i = left; i < right; i++) {
line.append(words[i]);
if (i < right - 1) {
appendSpaces(line, base + (i - left < extra ? 1 : 0));
}
}
return line.toString();
}
private void appendSpaces(StringBuilder line, int count) {
while (count-- > 0) {
line.append(' ');
}
}
}
func fullJustify(words []string, maxWidth int) []string {
ans := make([]string, 0)
idx := 0
for idx < len(words) {
left := idx
wordsLen := 0
for idx < len(words) &&
wordsLen+len(words[idx])+idx-left <= maxWidth {
wordsLen += len(words[idx])
idx++
}
ans = append(ans, buildJustifiedLine(
words, left, idx, wordsLen, maxWidth, idx == len(words),
))
}
return ans
}
func buildJustifiedLine(words []string, left, right, wordsLen, maxWidth int, lastLine bool) string {
line := make([]byte, 0, maxWidth)
gaps := right - left - 1
if lastLine || gaps == 0 {
for i := left; i < right; i++ {
if i > left {
line = append(line, ' ')
}
line = append(line, words[i]...)
}
return string(appendSpaces(line, maxWidth-len(line)))
}
spaces := maxWidth - wordsLen
base, extra := spaces/gaps, spaces%gaps
for i := left; i < right; i++ {
line = append(line, words[i]...)
if i < right-1 {
count := base
if i-left < extra {
count++
}
line = appendSpaces(line, count)
}
}
return string(line)
}
func appendSpaces(line []byte, count int) []byte {
for ; count > 0; count-- {
line = append(line, ' ')
}
return line
}
复杂度分析
设所有输入单词的字符总数为
C，最终产生R行。
- 时间复杂度：$O(C + R \times \text{maxWidth})$。每个单词只参与一次分组，构造答案时每个输出字符只写一次。
- 空间复杂度：$O(\text{maxWidth})$，不计返回结果。构造单行时的缓冲区最多保存
maxWidth个字符。
关键点总结
- 分组条件必须同时计入单词字符和「每两个单词至少一个空格」。
- 普通行均分的是全部剩余空格；除不尽时，额外空格从左往右分配。
- 最后一行和单词数为 1 的行统一按左对齐处理，避免间隔数为 0 时除零。
[left, right)使用左闭右开区间，单词数是right - left，间隔数少一个。- 面试讲解时先说清「贪心定边界、再按商和余数分空格」，代码会自然分成两个职责。
易错点总结
- 分组时只累计单词长度，漏掉最少间隔，会把放不下的单词塞进当前行。
- 用
spaces / wordCount均分空格：分母应是间隔数wordCount - 1。- 把余数空格补到右侧间隔；题目要求左侧间隔优先多一个空格。
- 最后一行仍按普通行均分，会得到居中效果；最后一行必须单空格连接并右侧补齐。
- 单词行直接计算
spaces / gaps会除零，必须与最后一行一起走左对齐分支。- 拼接结束后没有校验或补齐到
maxWidth，容易在单词行和最后一行少空格。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1451. 重新排列句子中的单词 | 中等 | 按长度稳定排序单词 |
| 6. Z 字形变换 | 中等 | 按行重排字符 |
| 38. 外观数列 | 中等 | 分组计数并构造字符串 |
| 8. 字符串转换整数 (atoi) | 中等 | 逐字符状态机解析 |
| 165. 比较版本号 | 中等 | 分段切分与补位比较 |
| 443. 压缩字符串 | 中等 | 原地读写双指针 |