题目描述

给定一个单词数组和一个最大宽度 maxWidth ，调整这个文本的格式，使得每行恰有 maxWidth 个字符，且左右对齐。
你需要遵循几个原则：

1. 每行要放尽可能多的单词；
2. 在单词之间填补空格，使得每行的长度是 maxWidth；
3. 单词之间的空格需要尽量均匀，如果空格数不能被（单词数量-1）整除，可让左边比右边多1；
4. 对于最后一行，只需实现左对齐，并且不用在单词之间添加额外空格；

注意：

• 单词是一个字符序列，由非空格字符组成；
• 每个单词的长度在0到 maxWidth 之间；
• 给定的字符数组至少包含一个单词；

样例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                  "
]

算法

(模拟) $O(n)$

一行一行处理，每次先求出这一行最多可以放多少个单词，然后分三种情况处理：

1. 如果是最后一行，则只实现左对齐：每个单词之间插入一个空格，行尾插入若干空格，使这一行的总长度是 maxWidth；
2. 如果这一行只有一个单词，则直接在行尾补上空格；
3. 其他情况，则需计算总共要填补多少空格，然后按题意均分在单词之间；

时间复杂度分析：每个单词只会遍历一遍，所以总时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    string space(int x)
    {
        string res;
        while (x -- ) res += ' ';
        return res;
    }

    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> res;
        for (int i = 0; i < words.size();)
        {
            int j = i + 1, s = words[i].size(), rs = words[i].size();
            while (j < words.size() && s + 1 + words[j].size() <= maxWidth)
            {
                s += 1 + words[j].size();
                rs += words[j].size();
                j ++ ;
            }
            rs = maxWidth - rs;
            string line = words[i];
            if (j == words.size())
            {
                for (i ++; i < j; i ++ )
                    line += ' ' + words[i];
                while (line.size() < maxWidth) line += ' ';
            }
            else if (j - i == 1) line += space(rs);
            else
            {
                int base = rs / (j - i - 1);
                int rem = rs % (j - i - 1);
                i ++ ;
                for (int k = 0; i < j; i ++, k ++ )
                    line += space(base + (k < rem)) + words[i];
            }
            i = j;
            res.push_back(line);
        }
        return res;
    }
};