68. 文本左右对齐

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            int j = i + 1;
            int len = words[i].length();
            // 求出一行能放多少个单词，并记录单词总长度+空隙个数
            while (j < words.length && len + 1 + words[j].length() <= maxWidth) {
                len += 1 + words[j].length();
                j++;
            }
            StringBuilder line = new StringBuilder();
            if (j == words.length || j == i + 1) {
                // 最后一行或只能放一个单词，就左对齐
                line.append(words[i]);
                for (int k = i + 1;k < j; k++) {
                    line.append(' ');
                    line.append(words[k]);
                }
                while (line.length() < maxWidth) {
                    line.append(' ');
                }
            } else {
                // 左右对齐
                int cnt = j - i - 1, r = maxWidth - len + cnt;
                line.append(words[i]);
                int a = r / cnt, b = r % cnt;
                for (int k = i + 1; k < j; k++) {
                    if (b-- > 0) {
                        // 前b个空隙是 a+1 个空格
                        for (int u = 0; u < a + 1; u++) {
                            line.append(' ');
                        }
                        line.append(words[k]);
                    } else {
                        // 后面的是 a 个空格
                        for (int u = 0; u < a; u++) {
                            line.append(' ');
                        }
                        line.append(words[k]);
                    }
                }
            }
            res.add(line.toString());
            i = j - 1;
        }
        return res;
    }
}