LeetCode 149. 直线上最多的点数

约 6 分钟
文章信息 12 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 10-20 面试经典 150 题 腾讯 字节 阿里 快手 B站 旷视
标签
数组 哈希表 数学 几何

题目描述

✅ 149. 直线上最多的点数

image-20260928220019535

image-20260928220019537

题意分析

给定平面上互不相同的点，求一条直线最多经过多少个点。点的输入顺序不代表几何位置，同一条直线可以从基准点向两个相反方向延伸。

若先选两个点确定直线，再扫描所有点判断是否在线上，需要三层枚举。固定一个基准点后，只要把其他点按经过基准点的直线分组，就能一次统计所有候选直线。

解法：枚举基准点 + 方向向量规范化

核心思路

[!blue]

固定点 i，点 j 相对它的方向向量为 (dx, dy)。经过同一基准点的两个向量只要成比例，对应的点就在同一条直线上。直接比较 dy / dx 会遇到竖直线除零和浮点精度问题，因此用整数对保存比例。

先求 gcd(abs(dx), abs(dy))，再把两个分量同时除以它，消除长度差异。约分后仍可能有正反两个表示，所以规定 dx 必须为正；若 dx == 0，则让 dy 为正。这样同一条线的所有向量都有唯一键，水平线与竖直线也分别统一为 (1, 0) 和 (0, 1)。

count[direction] 表示已经扫描到、与基准点形成该方向的其他点数。它不包含基准点，因此该直线经过的点数是 count[direction] + 1。哈希表必须随基准点重新创建，因为同一方向经过不同基准点时，可能代表不同的平行线。

内层只枚举 j > i。任取一条最优直线，其中下标最小的点作为基准点时，线上其余点都在它后面，并且会落到同一个键中。因此这样的枚举一定能完整统计最优直线，不需要同时扫描前面的点。

解题步骤

  1. 枚举基准点 i，为它创建方向计数表。
  2. 枚举 j > i，计算 dx = xj - xi、dy = yj - yi。
  3. 用最大公约数约分 dx、dy。
  4. 若 dx < 0，或 dx == 0 && dy < 0，同时翻转二者符号。
  5. 将规范化后的整数对作为哈希键并累加计数，用“计数 + 1”更新答案。

题目保证至少有一个点，所以答案从 1 开始；只有一个点时内层循环不会执行。所有点互不相同，保证 dx、dy 不会同时为零，最大公约数可以安全用于约分。坐标绝对值不超过 $10^4$，坐标差及其绝对值都在 int 范围内。

代码实现

class Solution {
    public int maxPoints(int[][] points) {
        int answer = 1;

        for (int i = 0; i < points.length; i++) {
            Map<String, Integer> count = new HashMap<>();

            for (int j = i + 1; j < points.length; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                // 用最大公约数约分方向，保持整数比较。
                int divisor = gcd(Math.abs(dx), Math.abs(dy));

                dx /= divisor;
                dy /= divisor;

                // 把相反向量也规范成同一方向，竖直方向单独统一符号。
                if (dx < 0 || (dx == 0 && dy < 0)) {
                    dx = -dx;
                    dy = -dy;
                }

                String direction = dx + "," + dy;
                int sameDirection = count.getOrDefault(direction, 0) + 1;

                count.put(direction, sameDirection);
                // 方向计数不含基准点，答案还要加上它。
                answer = Math.max(answer, sameDirection + 1);
            }
        }

        return answer;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int remainder = a % b;

            a = b;
            b = remainder;
        }

        return a;
    }
}

func maxPoints(points [][]int) int {
    answer := 1
    for i := 0; i < len(points); i++ {
        count := make(map[[2]int]int)
        for j := i + 1; j < len(points); j++ {
            dx := points[j][0] - points[i][0]
            dy := points[j][1] - points[i][1]
            // 用最大公约数约分方向，保持整数比较。
            divisor := gcd(abs(dx), abs(dy))
            dx /= divisor
            dy /= divisor

            // 把相反向量也规范成同一方向，竖直方向单独统一符号。
            if dx < 0 || dx == 0 && dy < 0 {
                dx = -dx
                dy = -dy
            }

            direction := [2]int{
                dx,
                dy,
            }
            count[direction]++
            // 方向计数不含基准点，答案还要加上它。
            if count[direction]+1 > answer {
                answer = count[direction] + 1
            }
        }
    }
    return answer
}

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func abs(value int) int {
    if value < 0 {
        return -value
    }
    return value
}

复杂度分析

  • 时间复杂度：$O(n^2 \log C)$，其中 $C$ 是坐标差的最大值；每对点计算一次最大公约数。坐标范围固定时通常记为 $O(n^2)$。
  • 空间复杂度：$O(n)$，固定一个基准点时，哈希表最多保存 $n-1$ 个方向。

关键点总结

[!green]

  • 枚举基准点后，二维共线问题转化为方向分组计数。
  • 用约分后的整数对表示方向，避免浮点精度和竖直线除零问题。
  • 最大公约数只消除倍数，符号规范化负责合并相反向量。
  • 哈希表不含基准点自身，因此局部计数要加 1。

易错点总结

[!yellow]

  • 使用 double 斜率可能把不同方向误判为相同，也必须额外处理 dx == 0。
  • 只做最大公约数约分、不统一符号，会把 (1,1) 和 (-1,-1) 分开。
  • 只统一 dx < 0 而漏掉竖直方向，会把 (0,1)、(0,-1) 分开。
  • 局部计数不含基准点，答案要加一；每换基准点必须新建计数表，不能混用不同直线。

相似题目

题目 难度 关联与区别
面试题 16.14. 最佳直线 中等 同样按锚点统计精确方向，原题还返回最早的两个下标并处理并列规则。
1232. 缀点成线 简单 原题只检查所有点是否同线，本题需要在多个候选方向中选最多的一组。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/56393194
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！