68. Text Justification

O(n) time
要确认一下单词长度是否会超过limit

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> res;
        for (int i = 0, n = words.size(); i < n;) {
            int cnt = 0, len = 0;
            while (i + cnt < n && len + words[i + cnt].length() + cnt <= maxWidth) { // 统计这一行所有单词的总长度以及个数
                len += words[i + cnt].length();
                ++cnt;
            }
            string line = words[i];
            for (int j = 1; j < cnt; ++j) {
                if (i + cnt >= n) { // 如果是最后一行，每个单词之间一个空格即可
                    line += " ";
                } else { // 否则按照下面的逻辑放空格，先平均放一样的空格数(maxWidth - len) / (cnt - 1)然后剩余的(maxWidth - len) % (cnt -1)个空格从前往后每个位置加一个，加完为止
                    line.append((maxWidth - len) / (cnt - 1) + (j <= (maxWidth - len) % (cnt - 1)), ' ');
                }
                line += words[i + j];
            }
            line.append(maxWidth - line.length(), ' '); // 不管是长单词单独一行还是最后一行，补齐空格
            res.push_back(line);
            i += cnt;
        }
        return res;
    }
};

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        int n = words.size(), cnt = -1; // cnt初始化为-1因为开始第一个单词前边不用加空格
        vector<int> indices; // 把每一行的单词的下标存起来
        vector<string> res;
        for (int i = 0; i < n; ++i) {
            if (cnt + 1 + words[i].length() <= maxWidth) { // 如果当前的单词能放在这一行上
                cnt += 1 + words[i].length(); // 加一个空格和当前单词
                indices.push_back(i); // 把当前单词的下标存起来
            } else {
                stack<int> spaces; // 计算每个单词前边的空格个数
                int slots = indices.size() - 1, total = maxWidth - cnt + slots; // 初始化有多少个位置要放空格以及这一行总的空格个数
                string s = words[indices[0]];
                if (slots == 0) { // 如果只有一个单词（超长单词）直接放即可
                    s.append(total, ' ');
                } else { // 如果不止一个单词
                    while (total > 0) { // 从后往前算平均数，比如18个空格5个单词，四个位置空格数分别为[5, 5, 4, 4]
                        int space = total / slots--;
                        spaces.push(space);
                        total -= space;
                    }
                    for (int j = 1; j < indices.size(); ++j) { // 算好空格数以后开始拼这行
                        s.append(spaces.top(), ' ').append(words[indices[j]]);
                        spaces.pop();
                    }
                }
                res.push_back(s);
                cnt = words[i].length(); // 结束这行以后cnt为当前单词长度，因为words[i]被挤下来了
                indices = {i}; // 结束这行以后indices放入当前单词下标
            }
            if (i == n - 1) { // 如果是最后一个单词，则肯定是最后一行，不计算空格数，直接放即可
                string s = words[indices[0]];
                for (int j = 1; j < indices.size(); ++j) {
                    s += " " + words[indices[j]];
                }
                s += string(maxWidth - s.length(), ' '); // 最后要补足空格
                res.push_back(s);
            }
        }
        return res;
    }
};