class Solution {
public List<String> fullJustify(String[] words, int maxWidth)
{
List<String> ans = new ArrayList<>();// 结果
List<String> list = new ArrayList<>();// 存当前行可容纳的单词
int n = words.length;
for (int i = 0; i < n;)
{
list.clear();// 清空上一行的单词
list.add(words[i]);// 题目保证每个单词的长度 <= maxWidth，所以每行肯定可以放一个单词
int lineLen = words[i++].length(); // 当前行的长度：单词 + 空格
while (i < n && lineLen + 1 + words[i].length() <= maxWidth)// 判断是否可以放多一个单词
{
lineLen += 1 + words[i].length();// 加上单词间的空格
list.add(words[i++]);
}
// 当前行是最后一行，特殊处理为 左对齐
if (i == n)
{
StringBuffer sb = new StringBuffer(list.get(0));
for (int j = 1; j < list.size(); j++)// 两两单词间加一个空格拼接起来
sb.append(" ").append(list.get(j));
while (sb.length() < maxWidth)// 用空格补全长度
sb.append(" ");
ans.add(sb.toString());
break;
}
// 当前行只有一个空格，左对齐 右边空格补全
int wordCnt = list.size();
if (wordCnt == 1)
{
String str = list.get(0);
while (str.length() != maxWidth)
str += " ";
ans.add(str);
continue;
}
// 一般情况
// 所有单词的总长度 = 行长度 - 单词间空格数量(wordCnt - 1)*1
int wordWidth = lineLen - (wordCnt - 1);
// 当前行空格总长度 = 最大长度 - 单词长度
int spaceWidth = maxWidth - wordWidth;
// 单词间的平均空格数量(向下取整)
int spaceItemWidth = spaceWidth / (wordCnt - 1);
String spaceItem = "";
for (int j = 0; j < spaceItemWidth; j++)
spaceItem += " ";
StringBuilder sb = new StringBuilder();
// j 枚举每个单词的下标；sum 记录当前空格的总数
for (int j = 0, sum = 0; j < wordCnt; j++)// 遍历当前行的每一个单词
{
String word = list.get(j);
sb.append(word);
if (j == wordCnt - 1)
break;// 最后一个单词不要加入 空格分割
sb.append(spaceItem);// 处理第一个单词时就把间隙要填的空格补上了
sum += spaceItemWidth;
// 剩余可填入的间隙数（两个单词间的间隙：即还剩多少个 spaceItem 要填）
// wordCnt-1：wordCnt 个单词有(wordCnt-1)个单词间隙
int remain = wordCnt - 1 - (j + 1);// (j+1) 下标偏移
// 剩余间隙 * 间隙长度 + 当前总空格长度 < 空格总长度
if (remain * spaceItemWidth + sum < spaceWidth)
{
sb.append(" ");// 当前间隙补多一个空格
sum++;
}
}
ans.add(sb.toString());
}
return ans;
}
}
