文本左右对齐
给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
注意:
- 单词是指由非空格字符组成的字符序列。
- 每个单词的长度大于 0，小于等于 maxWidth。
- 输入单词数组 words 至少包含一个单词。
示例 1:
codeType
输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
"This is an",
"example of text",
"justification. "
]
示例 2:
codeType
输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be",
因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。
示例 3:
codeType
输入: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 "
]
提示:
codeType
1 <= words.length <= 300
1 <= words[i].length <= 20
words[i] 由小写英文字母和符号组成
1 <= maxWidth <= 100
words[i].length <= maxWidth
解法：
这题在解法上没有什么思想难度，主要是处理流程比较复杂，注意空格的处理即可
typescript
function fullJustify(words: string[], maxWidth: number): string[] {
// 可以用贪心算法，一行一行计算当前行可以放多少单词，直到放不下
// 剩余的空格再均匀分配
const n = words.length
const resArr: string[] = []
let i = 0,// 单词索引
row = 0 // 行数
while(i<n){
let curWordLen = 0
let wordNum = 0
while(i < n){
if(wordNum === 0){ // 添加第一个单词时不需要考虑额外空格
// 单词超过最大长度
if(words[i].length > maxWidth) break
// 单词不超过最大长度
curWordLen += words[i].length
wordNum++
i++
}else{
// 单词+空格超长
if(curWordLen + words[i].length + 1 > maxWidth) break
curWordLen += words[i].length + 1 // 添加单词 +1 是空格的长度
wordNum++
i++
}
}
const remainWidth = maxWidth - curWordLen // 剩余空间
if(i === n || wordNum === 1){
// 如果是最后一行，或只有一个单词。最后一行默认左对齐
resArr.push('')
resArr[row] += words[i - wordNum] // 第一个单词直接拼接
for(let j=1; j<wordNum; j++){
resArr[row] += (' ' + words[i - wordNum + j])
}
const empty = new Array(remainWidth + 1).join(' ') // 用空格填充右边
resArr[row] += empty
}else{
// 有多个单词的情况,并且不是最后一行
// 分配剩余空间
const a1 = Math.floor(remainWidth / (wordNum - 1)) // 平均分配，减1是因为单词之间才需要空格
const a2 = remainWidth % (wordNum - 1) // 多余的空格，要按从左到右分配
// 组成该行字符串
resArr.push('') // push新的一行
resArr[row] += words[i - wordNum] // 第一个单词直接push
for(let j=1; j<wordNum; j++){ // 从第二个单词开始
let empty = new Array(1 + a1 + 1).join(' ') // 必备的一个空格+平均分配的空格（这种写法要再加1才是正确的空格数量）
if(j <= a2) empty += ' ' // 还有a2个空格要分配
resArr[row] += (empty + words[i - wordNum + j])
}
}
row++
}
return resArr
};