LeetCode 68. 文本左右对齐
题目描述
题意分析
保持单词顺序，每行放入尽可能多的单词，再补空格使长度恰好为
maxWidth。普通行要左右对齐，词间空格尽量均匀，多出的空格优先放在左侧间隔；最后一行以及只有一个单词的行左对齐，剩余空格补在末尾。
解法：逐行贪心分组并分配空格
核心思路
[!blue]
先确定本行包含哪些单词，再决定空格放在哪里。
left是本行起点，idx是尚未加入的第一个单词，wordsLen只统计已选单词的字符数。若加入words[idx]，本行会有idx-left+1个单词，至少需要idx-left个间隔空格，因此加入条件为wordsLen + words[idx].length() + idx-left <= maxWidth。一旦下一个单词放不下，继续加入只会使长度更大，当前的
[left, idx)就是按顺序能放入的最多单词。题目保证每个单词都不超过行宽，所以每轮至少放入一个单词，idx一定前进。普通行有
gaps = idx-left-1个间隔，要分配的空格总数为spaces = maxWidth-wordsLen。令base = spaces/gaps、extra = spaces%gaps，每个间隔先分base个，前extra个间隔再多分一个。这样恰好用完全部空格，任意两个间隔最多相差一个，也满足左侧优先。分组时已预留最少间隔，因此base至少为 1。最后一行要求词间只放一个空格；只有一个单词时没有可均分的间隔。这两种情况统一用单空格连接单词，再把剩余空格补到行尾。
解题步骤
- 从
idx指向的单词开始，累加单词长度；把必要的最少间隔也算入，直到下一个单词放不下。- 记录本行区间
[left, idx)、单词总长度wordsLen，判断它是否为最后一行。- 若是最后一行或只有一个单词，使用单空格连接，再在末尾补空格。
- 否则计算
spaces、gaps、平均空格数base和余数extra。- 从左到右拼接：前
extra个间隔放base + 1个空格，其余放base个。- 重复处理下一行，直到所有单词用完。
代码实现
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个字符。
关键点总结
[!green]
- 分组条件必须同时计入单词字符和「每两个单词至少一个空格」。
- 普通行均分的是全部剩余空格；除不尽时，额外空格从左往右分配。
- 最后一行和只有一个单词的行统一按左对齐处理，避免间隔数为 0 时除零。
[left, right)使用左闭右开区间，单词数是right - left，间隔数少一个。
易错点总结
[!yellow]
wordsLen不包含空格；选词时加入的是最少间隔，排版时分配的是maxWidth-wordsLen个全部空格，不能再额外补一轮分隔空格。- 普通行的分母是间隔数
wordCount-1；只有一个单词时必须先走左对齐分支，不能除以 0。- 判断最后一行要看选词后的
idx是否等于单词总数，即使它还能均分空格，也必须单空格连接、行尾补齐。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1592. 重新排列单词间的空格 | 简单 | 同样按单词间隙重新分配空格，原题处理整段文本，本题还需按宽度贪心分行并区分末行。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！