68 文本左右对齐

题目描述#

给定一个单词数组 words 和整数 maxWidth，需要把单词排成多行文本，并满足：

每行长度恰好为 maxWidth
除最后一行外，左右两端对齐
单词间空格尽量均匀分配；如果不能均分，左侧间隙比右侧多
最后一行左对齐，单词间只放一个空格，末尾补空格

知识边界#

这题本质是贪心 + 字符串模拟。

核心思路与代码一一对应：

用 start 记录当前行起点，col 记录当前行单词数，nums 记录当前行单词总长度（不含空格）。
从左到右尝试把新单词放进当前行；若发现放不下（maxWidth-nums < col-1），就把这行先结算。
结算非最后一行时：
- 若只有一个单词：右侧补空格到 maxWidth
- 否则计算：
  - avg = spaceNum / (col-1)：每个间隔的基础空格
  - extra = spaceNum % (col-1)：前 extra 个间隔多 1 个空格
所有单词扫描结束后，单独处理最后一行：单词间只加一个空格，末尾补齐。

易错点：

判断“放不下”后要先回退当前单词，再结算上一行
只有一个单词时不能走均分逻辑
最后一行规则与普通行不同，需要单独处理

时间复杂度：O(n + L)，其中 n 为单词数，L 为输出总字符数（构造答案所需）
空间复杂度：O(L)（答案占用，额外变量为常数级）

代码#

func fullJustify(words []string, maxWidth int) []string {
    col  := 0
    ans  := []string{}
    nums := 0
    start := 0

    for i, x := range words {
        nums += len(x)
        col  += 1

        if maxWidth-nums < col-1 {
            // 回退：当前单词放不下
            col  -= 1
            nums -= len(x)

            spaceNum := maxWidth - nums
            line := ""

            if col == 1 {
                // 单词只有一个：右填充空格
                line += words[start]
                for len(line) < maxWidth {
                    line += " "
                }
            } else {
                avg   := spaceNum / (col - 1) // 每个间隔基础空格数
                extra := spaceNum % (col - 1) // 前 extra 个间隔多一个空格

                for j := start; j < start+col; j++ {
                    line += words[j]
                    if j < start+col-1 {
                        spaces := avg
                        if j-start < extra {
                            spaces++ // 前 extra 个间隔多一个空格
                        }
                        for k := 0; k < spaces; k++ {
                            line += " "
                        }
                    }
                }
            }

            ans   = append(ans, line)
            start = i
            nums  = len(x)
            col   = 1
        }
    }

    // 最后一行：单词间单个空格，末尾补齐
    lastLine := ""
    for i := start; i < len(words); i++ {
        if i > start {
            lastLine += " "
        }
        lastLine += words[i]
    }
    for len(lastLine) < maxWidth {
        lastLine += " "
    }
    ans = append(ans, lastLine)

    return ans
}