LeetCode 68. 文本左右对齐 (Text Justification) 详细题解

2025-08-06

题目描述

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

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

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

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

注意:

  • 单词是指由非空格字符组成的字符序列。
  • 每个单词的长度大于 0，小于等于 maxWidth。
  • 输入单词数组 words 不包含前导或尾随空格。
  • words[0].length <= maxWidth
  • 至少有一个单词。

解题思路

这道题的核心是 贪心策略。我们每次都尽可能多地选择单词放入当前行，直到再放一个单词就会超出 maxWidth 为止。当确定了一行的单词后，我们再根据这一行是普通行还是特殊行（最后一行或单单词行）来分配空格。

具体步骤如下：

  1. 确定每行的单词：使用一个指针 i 指向当前行的第一个单词，另一个指针 j 向后遍历，以确定当前行能容纳多少个单词。
  2. 分配空格：
    • 普通行：如果当前行不是最后一行，并且包含多个单词，我们需要均匀地分配空格。计算出总共需要的空格数，然后计算每个单词间隙平均可以放多少个空格，以及多余的空格数。将多余的空格从左到右依次分配给每个间隙。
    • 特殊行：如果当前行是最后一行，或者只包含一个单词，那么它需要左对齐。单词之间只用一个空格隔开，行尾用空格填充至 maxWidth。
  3. 循环处理：重复以上步骤，直到所有单词都被处理完毕。

代码实现

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        int n = words.length;
        int i = 0;
        while(i < n){
            int j = i + 1;
            int len = words[i].length();
            while(j < n && len + words[j].length() + (j - i - 1) < maxWidth){
                len += words[j].length();
                j++;
            }
            int numWords = j - i;
            StringBuilder line = new StringBuilder();
            if(j==n || numWords==1){
                for(int k = i; k < j; k++){
                    line.append(words[k]);
                    if(k<j-1){
                        line.append(" ");
                    }
                }
                while(line.length() < maxWidth){
                    line.append(" ");
                }
            }else{
                int totalSpaces = maxWidth - len;
                int wordSpaces = totalSpaces / (numWords - 1);
                int extraSpaces = totalSpaces % (numWords - 1);
                for(int k = i; k < j; k++){
                    line.append(words[k]);
                    if(k < j - 1){
                        int realSpaces = wordSpaces + (k - i < extraSpaces ? 1 : 0);
                        for(int l = 0; l < realSpaces; l++){
                            line.append(" ");
                        }
                    }
                }
            }
            result.add(line.toString());
            i = j;
        }
        return result;
    }
}

核心逻辑详解

接下来，我们详细分析代码中的核心逻辑。

1. while(j < n && len + words[j].length() + (j - i - 1) < maxWidth) 详解

这个 while 循环的目的是确定当前行能容纳哪些单词。

  • i 是当前行第一个单词的索引。
  • j 是一个试探性的指针，用来指向下一个要尝试放入该行的单词。
  • len 记录了从 words[i] 到 words[j-1] 这些单词的纯字符总长度（不包含任何空格）。

循环条件 len + words[j].length() + (j - i - 1) < maxWidth 是这道题最关键的部分之一。我们来分解它：

  • len: 已经放入行的单词的总长度（纯字符，不含空格）。
  • words[j].length(): 准备要放入的新单词的长度。
  • (j - i - 1): 这部分是理解的关键。这个值表示的是当前已经在行内的单词之间的间隙数量。注意，这里计算的是 words[i] 到 words[j-1] 之间的间隙，不包括 words[j-1] 和 words[j] 之间的空格。
    • 如果当前行已有 j - i 个单词（从 words[i] 到 words[j-1]），它们之间有 (j - i) - 1 个间隙。
    • 例如：2个单词之间有1个间隙，3个单词之间有2个间隙。
    • 为了满足文本对齐的基本要求，每个间隙至少需要一个空格。
    • 所以 (j - i - 1) 代表了当前行内已有单词之间所需的最少空格数。

完整条件的含义： len + words[j].length() + (j - i - 1) 表示：

  • 当前行已有单词的总长度 (len)
  • 加上新单词的长度 (words[j].length())
  • 加上当前行内单词之间的最少空格 (j - i - 1)
  • 注意：这里没有加上 words[j-1] 和 words[j] 之间的空格，因为如果 words[j] 能放入，它们之间至少需要1个空格，这会在下一次循环中通过 j - i - 1 体现出来。

实际上，当我们尝试放入 words[j] 时，完整的长度应该是： len + words[j].length() + (j - i) （包括 words[j-1] 和 words[j] 之间的1个空格）

但代码写的是 (j - i - 1)，这是因为在下一次循环更新 len 时，只累加了单词长度，没有累加空格。这样的写法等价于：

  • 当前检查：len + words[j].length() + (j - i - 1) < maxWidth
  • 等价于：len + words[j].length() + (j - i - 1) + 1 <= maxWidth
  • 即：len + words[j].length() + (j - i) <= maxWidth

举例分析： 假设 maxWidth = 20, i = 0, words[0]="This", words[1]="is", words[2]="an".

  1. 初始状态: i=0, j=1, len = words[0].length() = 4.
  2. 尝试放入 words[1] (“is”):
    • j=1
    • len (当前单词总长) = 4 (只有 “This”)
    • words[1].length() = 2 (“is”)
    • 当前行内单词间隙数 j - i - 1 = 1 - 0 - 1 = 0 (因为只有1个单词 “This”，没有间隙)
    • 总长度 = 4 + 2 + 0 = 6. 6 < 20，成立。
    • 可以放入。更新 len: len = 4 + 2 = 6。j 变为 2。
  3. 尝试放入 words[2] (“an”):
    • j=2
    • len (当前单词总长) = 6 (“This” + “is”)
    • words[2].length() = 2 (“an”)
    • 当前行内单词间隙数 j - i - 1 = 2 - 0 - 1 = 1 (“This” 和 “is” 之间有1个间隙)
    • 总长度 = 6 + 2 + 1 = 9. 9 < 20，成立。
    • 可以放入。更新 len: len = 6 + 2 = 8。j 变为 3。

假如 words[3]="example"，长度为 7。

  1. 尝试放入 words[3] (“example”):
    • j=3
    • len (当前单词总长) = 8 (“This” + “is” + “an”)
    • words[3].length() = 7 (“example”)
    • 当前行内单词间隙数 j - i - 1 = 3 - 0 - 1 = 2 (“This”-“is” 和 “is”-“an” 两个间隙)
    • 总长度 = 8 + 7 + 2 = 17. 17 < 20，成立。
    • 可以放入。更新 len: len = 8 + 7 = 15。j 变为 4。

… 以此类推，直到条件不满足，循环结束。

2. int numWords = j - i; 如何理解？

这个非常直接。i 是当前行第一个单词的索引，当 while 循环结束时，j 指向的是下一个不能被放入当前行的单词的索引。

因此，当前行的单词索引范围是 [i, i+1, ..., j-1]。

这是一个左闭右开的区间 [i, j)。区间的长度，也就是单词的数量，就是 j - i。

举例分析： 假设循环结束后，i = 3, j = 7。

  • 这意味着当前行的单词是 words[3], words[4], words[5], words[6]。
  • words[7] 因为太长而无法放入。
  • 单词数量 numWords = 7 - 3 = 4。

3. k - i < extraSpaces 如何理解？

这行代码用于处理空格的非均匀分配。

当一行确定下来后（并且它不是特殊行），我们需要在单词之间填充空格。

  • numWords = j - i: 当前行的单词数。
  • len: 当前行所有单词的纯字符总长度。
  • totalSpaces = maxWidth - len: 需要填充的总空格数。
  • numWords - 1: 单词间的间隙数量。例如，4个单词有3个间隙。
  • wordSpaces = totalSpaces / (numWords - 1): 每个间隙平均能分到的空格数。
  • extraSpaces = totalSpaces % (numWords - 1): 平均分配后，剩余的、需要额外分配的空格数。

题目要求，如果空格不能均分，多余的空格要从左边的间隙开始依次分配。

k 是 for 循环中当前单词的索引，范围是 [i, j-1]。 k - i 表示当前单词相对于行首的位置（从0开始计数）。

  • 当 k=i 时，k-i=0，处理第一个间隙（words[i] 和 words[i+1] 之间）。
  • 当 k=i+1 时，k-i=1，处理第二个间隙。
  • …

k - i < extraSpaces 这个条件的意思是：如果当前间隙的序号（从0开始）小于多余的空格数，那么这个间隙就多分一个空格。

举例分析: 假设 maxWidth = 20, words = ["This", "is", "an", "example"] 都在这一行。

  • numWords = 4
  • len = 4 + 2 + 2 + 7 = 15
  • totalSpaces = 20 - 15 = 5
  • 间隙数 numWords - 1 = 3
  • wordSpaces = 5 / 3 = 1 (每个间隙至少1个空格)
  • extraSpaces = 5 % 3 = 2 (还有2个多余的空格需要分配)

现在我们用循环来构建这一行： for(int k = i; k < j; k++) (这里 i=0, j=4)

  1. k = 0 (处理 “This”):
    • line.append(words[0]) -> "This"
    • k < j - 1 (0 < 3) 为 true。
    • k - i < extraSpaces -> 0 - 0 < 2 -> 0 < 2 为 true。
    • 当前间隙获得 wordSpaces + 1 = 1 + 1 = 2 个空格。
    • line -> "This " (2个空格)
  2. k = 1 (处理 “is”):
    • line.append(words[1]) -> "This is"
    • k < j - 1 (1 < 3) 为 true。
    • k - i < extraSpaces -> 1 - 0 < 2 -> 1 < 2 为 true。
    • 当前间隙获得 wordSpaces + 1 = 1 + 1 = 2 个空格。
    • line -> "This is " (2个空格)
  3. k = 2 (处理 “an”):
    • line.append(words[2]) -> "This is an"
    • k < j - 1 (2 < 3) 为 true。
    • k - i < extraSpaces -> 2 - 0 < 2 -> 2 < 2 为 false。
    • 当前间隙获得 wordSpaces = 1 个空格。
    • line -> "This is an " (1个空格)
  4. k = 3 (处理 “example”):
    • line.append(words[3]) -> "This is an example"
    • k < j - 1 (3 < 3) 为 false。不加空格。

最终结果: "This is an example"，长度为 20。前两个间隙分配了2个空格，最后一个间隙分配了1个空格，符合要求。

总结

LeetCode 68 是一道考验细节处理能力的题目。核心思想是贪心，但成败在于对边界条件的精确处理：

  1. 行单词确定：准确计算包含最少空格在内的行长度是关键。
  2. 空格分配：理解整除和取模运算在均匀/非均匀分配中的作用。
  3. 边界判断：清晰地区分“普通行”与“特殊行”（最后一行、单单词行），并采用不同的对齐策略。

希望这篇详细的分析能帮助你彻底理解这道题目！