68. 文本左右对齐
给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
注意:
- 单词是指由非空格字符组成的字符序列。
- 每个单词的长度大于 0，小于等于 maxWidth。
- 输入单词数组
words至少包含一个单词。
示例 1:
输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
"This is an",
"example of text",
"justification. "
]
示例 2:
输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解释: 注意最后一行的格式应为 "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 "
]
提示:
1 <= words.length <= 3001 <= words[i].length <= 20words[i]由小写英文字母和符号组成1 <= maxWidth <= 100words[i].length <= maxWidth
题解：
分组循环
适用场景：按照题目要求，数组会被分割成若干组，每一组的判断/处理逻辑是相同的。
核心思想：
外层循环负责遍历组之前的准备工作（记录开始位置），和遍历组之后的统计工作（更新答案）。
内层循环负责遍历组，找出这一组最远在哪结束。
这个写法的好处是，各个逻辑块分工明确，也不需要特判最后一组（易错点）。以我的经验，这个写法是所有写法中最不容易出 bug 的，推荐大家记住。
内层循环开始前
记录当前位置 start=i，这也是这一行第一个单词的下标。
初始化这一行的最小长度 sumLen 为 words[i] 的长度。
内层循环
从这一行的第二个单词 i+1 开始循环。
从第二个单词开始，每个单词之前必须有一个空格。
所以每个单词占用的长度是单词长度加一，加给 sumLen。
如果 sumLen+len(words[i])+1>maxWidth，退出循环。
内层循环结束后
这一行还剩下 extraSpaces=maxWidth−sumLen 个空格没有分配。
这一行单词之间的空隙个数 gaps=i−start−1，即单词个数减一。
首先处理特殊情况。如果只有一个单词，或者现在是最后一行，那么根据题目要求，所有单词左对齐，单词之间只有一个空格，末尾补上 extraSpaces 个空格。
然后处理一般情况。
单词之间至少有 ⌊
gaps
extraSpaces
⌋+1 个空格。其中 +1 是因为单词之间必须有一个空格，不算在 extraSpaces 中，这里重新加进来。
还剩下 rem=extraSpacesmodgaps 个空格，分配给前 rem 个空隙。换句话说，前 rem+1 个单词之间的空格个数多 1。
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> ans = new ArrayList<>();//存储答案不定长数组列表ArrayList
int n = words.length; // length 是数组对象的属性，直接.length 获取而不用.length();
for (int i = 0; i < n; ) { // 外层循环，用于记录内循环的行的开始位置，以及遍历后的统计，i由内层循环控制
int start = i; // 这轮循环第一个单词的下标，第一次循环下标为0开始
int sumLen = words[i].length(); // 第i个单词的长度
for (i++; i<n && sumLen + words[i].length() + 1 <= maxWidth;i++) { // i++ 因为第一个单词已经算进 `sumLen` 了，所以从**第二个单词word[2]**开始试探，如果长度加起来放得下就就更新 sumLen 并且更新i准备判断下一个单词word[3]能否放入
sumLen += words[i].length() + 1;
}
int extraSpaces = maxWidth - sumLen; // 这一行剩余的可分配的空格数
int gaps = i - start -1; // 这一行的空隙数（单词个数（i(现在在哪给单词) - start(这一行初始在哪个单词)）减一） 如 i = 0; 初始一个单词，放入一个单词后 i 经过 ++i, i++,i变为2， 2-0 =2两个单词，1个间隔
// 先处理特殊情况：如果只有一个单词，或者是最后一行，那么左对齐，末尾补空格
if (gaps == 0 || i == n) { // gaps=0,只有一个单词，没有间隔，或者i为最后一个单词n了
String row = join(words, start, i, " ") + " ".repeat(extraSpaces);
ans.add(row);
continue;
}
// 一般情况：把 extraSpaces 个空格均匀分配到 gaps 个空隙中（靠左的空格更多）
int avg = extraSpaces / gaps;
int rem = extraSpaces % gaps;
String spaces = " ".repeat(avg + 1); // +1 表示加上单词之间已有的一个空格
String row = join(words, start, start + rem + 1, spaces + ' ') + // 前 rem 个空隙多一个空格
spaces + join(words, start + rem + 1, i, spaces);
ans.add(row);
}
return ans;
}
// 用 StringBuilder 的写法见【Java 写法二】
private String join(String[] words, int start, int end, String sep) {
return String.join(sep, Arrays.copyOfRange(words, start, end));
}
}
复杂度分析
时间复杂度：O(nL+maxWidth)，其中 n 是 words 的长度，L≤20 是 words[i] 的最大长度。虽然写了个二重循环，但是内层循环中对 i 加一的总执行次数不会超过 n 次，所以总的循环次数是 O(n) 的。最后一行需要 O(maxWidth) 的时间，其余行消耗的时间之和是 O(nL)。你可能会问，如果每一行都只有一个单词呢？这种情况下 2L+1>maxWidth，又由于 L≤maxWidth，所以 L 和 maxWidth 是同阶的，此时 O(nL)=O(n⋅maxWidth)。
空间复杂度：O(nL+maxWidth)。最后一行需要 O(maxWidth) 的空间，其余行消耗的空间之和是 O(nL)。
作者：灵茶山艾府
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。