LeetCode 149. 直线上最多的点数

◎

本节目标

以最大公约数约分并统一符号，统计同一直线方向的点。

查看原题

返回博弈与计算几何框架

题意与约束

给定平面整数点，求同一条直线上最多的点数。点可能重复，坐标可为负。

第一反应与瓶颈

枚举任意两点确定直线，再扫描所有点是 O(n³)。浮点斜率还会因精度和符号形式使同一方向无法稳定作为哈希键。

数学关系与算法推导

固定一个锚点，所有与它共线的其他点应拥有相同方向 (dx, dy)。用 gcd(|dx|, |dy|) 约分；垂直线统一成 (0,1)，水平线统一成 (1,0)，其余让 dx > 0。相同点单独计入重复数。

正确性依据

对固定锚点，任意同一直线上的非重复点方向成比例，约分与符号规则会映射到同一键；不同方向不可能映射成同一最简有向比例。键的最大频次加上锚点及重复点，正是以该锚点为代表的最长直线。

样例执行过程

(0,0)、(1,-1)、(2,-2) 的方向分别为 (1,-1) 与 (2,-2)，约分后相同，计数为三。两个 (1,1) 是重复点，要加到与 (2,2) 的方向计数上。

代码实现

C++

C++17

#include <algorithm>
#include <cstdlib>
#include <map>
#include <numeric>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int best = 0;
        for (int i = 0; i < static_cast<int>(points.size()); i++) {
            map<pair<long long, long long>, int> counts;
            int duplicates = 1;
            int localBest = 0;
            for (int j = i + 1; j < static_cast<int>(points.size()); j++) {
                long long dx = static_cast<long long>(points[j][0]) - points[i][0];
                long long dy = static_cast<long long>(points[j][1]) - points[i][1];
                if (dx == 0 && dy == 0) {
                    duplicates++;
                    continue;
                }
                const long long divisor = gcd(llabs(dx), llabs(dy));
                dx /= divisor;
                dy /= divisor;
                if (dx == 0) {
                    dy = 1;
                } else if (dy == 0) {
                    dx = 1;
                } else if (dx < 0) {
                    dx = -dx;
                    dy = -dy;
                }
                localBest = max(localBest, ++counts[{dx, dy}]);
            }
            best = max(best, localBest + duplicates);
        }
        return best;
    }
};

Python

Python 3

from collections import defaultdict
from math import gcd


class Solution:
    def maxPoints(self, points: list[list[int]]) -> int:
        best = 0
        for i, (x1, y1) in enumerate(points):
            counts: dict[tuple[int, int], int] = defaultdict(int)
            duplicates = 1
            local_best = 0
            for x2, y2 in points[i + 1:]:
                dx = x2 - x1
                dy = y2 - y1
                if dx == 0 and dy == 0:
                    duplicates += 1
                    continue
                divisor = gcd(abs(dx), abs(dy))
                dx //= divisor
                dy //= divisor
                if dx == 0:
                    dy = 1
                elif dy == 0:
                    dx = 1
                elif dx < 0:
                    dx = -dx
                    dy = -dy
                counts[(dx, dy)] += 1
                local_best = max(local_best, counts[(dx, dy)])
            best = max(best, local_best + duplicates)
        return best

复杂度分析

• C++ 时间复杂度：O(n²(log C + log n))。每对点用 GCD 规范化方向需要 O(log C)，std::map 的查询与插入需要 O(log n)。
• Python 平均时间复杂度：O(n² log C)。GCD 需要 O(log C)，字典查询与插入平均为 O(1)。
• 空间复杂度：O(n)，每个锚点保存方向计数。

边界与易错点

• 先处理重复点，不能对 (0,0) 方向求 GCD 后入表。
• (-1,1) 与 (1,-1) 表示同一直线方向，必须统一符号。
• 坐标差和绝对值使用足够宽的整数，避免减法边界溢出。

模式迁移

将等价对象转成唯一规范键，是哈希统计的重要技巧；可迁移到分数、向量比例、无向边和旋转后的等价状态。