给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

说明:

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。
示例:

输入:
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 "
]

java代码：

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {

        ArrayList<String> list = new ArrayList<>();

        if(words.length == 1){
            String s = addSpace(words[0], maxWidth - words[0].length());
            list.add(s);
            return list;
        }

        int index = 0;

        while (index < words.length){

            ArrayList<Integer> tempList = new ArrayList<>();
            String s = "";
            int length = 0;
            while (index < words.length){
                s = s + words[index];
                length = length + words[index].length() ;
                if(length <= maxWidth){
                    length++;
                    tempList.add(index);
                    index++;
                }else {
                    length = length - 1 - words[index].length();
                    s = s.substring(0,s.length() - words[index].length());
                    break;
                }
            }

            //最后一行
            if(index == words.length){
                String res = "";
                for(int i = 0; i < tempList.size(); i++){
                    res =res +  words[tempList.get(i)] + " ";
                }
                if(maxWidth - res.length() >= 0) {
                    res = addSpace(res, maxWidth - res.length());
                }else {
                    res = res.substring(0,res.length() - 1);
                }
                list.add(res);
                break;
            }else if(tempList.size() > 1) {
                String res = "";

                //计算空格
                int m = (maxWidth - s.length()) / (tempList.size() - 1);
                int n = (maxWidth - s.length()) % (tempList.size() - 1);
                for(int i = 0; i < tempList.size(); i++){
                    res = res + words[tempList.get(i)];
                    if(i == tempList.size() - 1){
                        res = addSpace(res,0);
                    }else {
                        if(n > 0) {
                            res = addSpace(res, m+1);
                            n--;
                        }else {
                            res = addSpace(res,m);
                        }
                    }
                }
                list.add(res);
            }else if(tempList.size() == 1){
                String res = s;
                res = addSpace(res,maxWidth - s.length());
                list.add(res);
            }
        }

        return list;

    }


    public String addSpace(String word,int num){
        String res = word;
        for(int i = 0; i < num; i++){
            res = res + " ";
        }
        return res;
    }
}