LeetCode 149 - 直线上最多的点数（Max Points on a Line）

问题描述

给定一个二维平面上的点数组 points，其中 points[i] = [xi, yi]，返回位于同一直线上的最大点数。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：3
解释：
所有点都在直线 y = x 上

示例 2：

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4
解释：
最多有 4 个点在同一直线上

约束条件：

1 <= points.length <= 300
points[i].length == 2
-10^4 <= xi, yi <= 10^4
所有点都是唯一的

解题思路

核心算法概念

这道题的核心思想是：对于每个点，计算它与所有其他点形成的直线斜率，统计具有相同斜率的点的数量。

关键洞见

斜率表示直线：两点确定一条直线，斜率是直线的唯一标识
避免浮点数精度问题：直接使用分数表示斜率，而不是浮点数
处理重复点：需要单独统计与基准点重合的点
最简分数：使用最大公约数将斜率化为最简形式

解题步骤

步骤 1：枚举基准点

遍历每个点作为基准点
对于每个基准点，计算它与所有其他点形成的直线

步骤 2：计算斜率

对于基准点 (x1, y1) 和另一个点 (x2, y2)
斜率 = (y2 - y1) / (x2 - x1)
使用最简分数表示：(dy/gcd(dx, dy), dx/gcd(dx, dy))

步骤 3：统计共线点

使用哈希表记录每个斜率对应的点数
同时统计与基准点重合的点数
最终结果 = 重合点数 + 最大斜率对应的点数

实现细节

斜率计算优化

为了避免浮点数精度问题，我们使用最简分数表示斜率：

dx := points[j][0] - points[i][0]
dy := points[j][1] - points[i][1]
g := gcd(dx, dy)
slope := [2]int{dx / g, dy / g}

重复点处理

对于与基准点重合的点，我们需要单独统计：

if points[j][0] == points[i][0] && points[j][1] == points[i][1] {
    duplicates++
    continue
}

边界情况处理

当点数 ≤ 2 时，直接返回点数
处理垂直线（dx = 0）和水平线（dy = 0）的情况

代码实现

func maxPoints(points [][]int) int {
    n := len(points)
    if n <= 2 {
        return n
    }

    res := 0

    // 枚举每个点作为基准点
    for i := 0; i < n; i++ {
        hashTable := map[[2]int]int{}
        duplicates := 1  // 统计与基准点重合的点数
        
        // 计算与其他点形成的直线斜率
        for j := i + 1; j < n; j++ {
            // 处理重复点
            if points[j][0] == points[i][0] && points[j][1] == points[i][1] {
                duplicates++
                continue
            }
            
            // 计算斜率（使用最简分数表示）
            dx := points[j][0] - points[i][0]
            dy := points[j][1] - points[i][1]
            g := gcd(dx, dy)
            hashTable[[2]int{dx / g, dy / g}]++
        }
        
        // 更新结果
        if res < duplicates {
            res = duplicates
        }
        for _, count := range hashTable {
            if res < count + duplicates {
                res = count + duplicates
            }
        }
    }
    return res
}

// 计算最大公约数
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}

执行过程分析

以示例 2 为例：[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

基准点 (1,1)：
- 与 (3,2) 的斜率：(2-1)/(3-1) = 1/2
- 与 (5,3) 的斜率：(3-1)/(5-1) = 2/4 = 1/2
- 与 (4,1) 的斜率：(1-1)/(4-1) = 0/3 = 0/1
- 与 (2,3) 的斜率：(3-1)/(2-1) = 2/1
- 与 (1,4) 的斜率：(4-1)/(1-1) = 3/0（垂直线）
结果：最多 2 个点共线（斜率为 1/2）
基准点 (3,2)：
- 与 (5,3) 的斜率：(3-2)/(5-3) = 1/2
- 与 (4,1) 的斜率：(1-2)/(4-3) = -1/1
- 与 (2,3) 的斜率：(3-2)/(2-3) = 1/-1 = -1/1
- 与 (1,4) 的斜率：(4-2)/(1-3) = 2/-2 = -1/1
结果：最多 3 个点共线（斜率为 -1/1）

最终答案为 4。

方法比较

方面	哈希表法	暴力枚举法
时间复杂度	O(n²)	O(n³)
空间复杂度	O(n)	O(1)
优点	高效，避免重复计算	直观易懂
缺点	实现相对复杂	运行时间过长
推荐度	★★★★★	★★☆☆☆

复杂度分析

时间复杂度：O(n²)

外层循环：O(n)
内层循环：O(n)
总时间复杂度：O(n²)

空间复杂度：O(n)

哈希表存储斜率信息：O(n)
在最坏情况下，所有点都不共线，哈希表大小为 O(n)

详细推导

对于每个基准点，我们需要：

计算与 n-1 个其他点的斜率：O(n)
哈希表操作（插入和查找）：O(1) 平均情况
总操作数：n × (n-1) = O(n²)

关键收获

重要算法概念

几何问题的数学建模：将几何问题转化为数学计算
哈希表的应用：使用哈希表高效统计和查找
精度处理技巧：避免浮点数精度问题，使用分数表示

常见陷阱

浮点数精度问题：直接使用浮点数计算斜率可能导致精度误差
重复点处理：忘记统计与基准点重合的点
边界情况：没有正确处理垂直线和水平线

应用场景

计算机图形学中的直线检测
图像处理中的特征点匹配
地理信息系统中的路径规划

总结：这道题通过巧妙使用哈希表和数学技巧，将几何问题转化为高效的算法问题。关键在于理解斜率作为直线唯一标识的概念，以及如何避免浮点数精度问题。

Adrian Wang's blog