LeetCode 面试题 16.14. 最佳直线
目录
题目描述
题意分析
给定互不相同的二维点，找一条经过点数最多的直线，返回能确定这条直线的两个点的下标
[i, j]。若有多组答案，先选 i 较小的，再选 j 较小的。题目既要最大点数，又把下标字典序写进答案规则。直接用“斜率到次数”的哈希表能做到
O(n^2)，但斜率约分、正负号、竖直线以及如何恢复最小 j 都容易把实现拖复杂。点数规模允许时，枚举点对再扫描其余点更适合白板：逻辑直接，天然按字典序访问候选。判定三点共线不能依赖浮点斜率。对点
A、B、C，只需比较叉积(By-Ay)(Cx-Ax) = (Cy-Ay)(Bx-Ax)；竖直线、水平线都统一包含在公式里。
解法：枚举点对 + 叉积判共线
核心思路
外层按 i 升序、内层按 j 升序枚举一条候选直线。对固定
(i,j)，从k = j + 1开始扫描并统计共线点，计数初值为 2。循环不变量是：处理到 k 前，
cnt等于点 i、j 加上区间(j,k)中所有与它们共线的点数。叉积相等就把当前点计入。为什么不扫描 j 之前的点？如果某条最优直线还包含更早的点，那么它会在更早的
(i,j)组合中被完整统计；而题目恰好要求最小下标对。按字典序枚举并且只在cnt > best时更新，第一次达到最大值的候选会被保留，后续并列不会覆盖它。Java 使用
long、Go 使用int64计算叉积，避免两个坐标差相乘时溢出。
解题步骤
- 初始化
best = 0和答案数组。- 枚举第一个下标 i，再枚举
j > i。- 令
cnt = 2，扫描k > j。- 用整数叉积判断 i、j、k 是否共线，共线则
cnt++。- 仅当
cnt > best时记录[i,j]；相等时保持旧答案以满足字典序。例：
points = [[0,0],[1,1],[1,0],[2,2]]。候选(0,1)扫描后发现点 3 共线，cnt = 3，记录[0,1]；其他点对最多得到 2 或同属这条线但下标更大，均不会覆盖答案，最终返回[0,1]。
代码实现
class Solution {
public int[] bestLine(int[][] points) {
int n = points.length;
int mx = 0;
int[] answer = new int[2];
for (int i = 0; i < n; ++i) {
int x1 = points[i][0], y1 = points[i][1];
for (int j = i + 1; j < n; ++j) {
int x2 = points[j][0], y2 = points[j][1];
int cnt = 2;
for (int k = j + 1; k < n; ++k) {
int x3 = points[k][0], y3 = points[k][1];
long a = (long) (y2 - y1) * (x3 - x1);
long b = (long) (y3 - y1) * (x2 - x1);
if (a == b) {
++cnt;
}
}
if (mx < cnt) {
mx = cnt;
answer[0] = i;
answer[1] = j;
}
}
}
return answer;
}
}
func bestLine(points [][]int) []int {
n := len(points)
answer := make([]int, 2)
mx := 0
for i := 0; i < n; i++ {
x1, y1 := points[i][0], points[i][1]
for j := i + 1; j < n; j++ {
x2, y2 := points[j][0], points[j][1]
cnt := 2
for k := j + 1; k < n; k++ {
x3, y3 := points[k][0], points[k][1]
a := int64(y2-y1) * int64(x3-x1)
b := int64(y3-y1) * int64(x2-x1)
if a == b {
cnt++
}
}
if mx < cnt {
mx = cnt
answer[0], answer[1] = i, j
}
}
}
return answer
}
复杂度分析
- 时间复杂度：
O(n^3)，共有O(n^2)个点对，每对最多扫描O(n)个后续点。- 空间复杂度：
O(1)，不计返回数组只使用常数变量。
关键点总结
- 叉积判共线统一覆盖普通、水平和竖直直线，没有浮点精度与除零分支。
- 外层枚举顺序与“下标最小”规则一致，严格大于才更新是 tie-break 的关键。
- 三重循环看似朴素，但状态少、证明短；面试官追问优化时，再给出“固定 i，用约分后的
(dy,dx)计数”的O(n^2)哈希方案。- 叉积要提升到宽整数后再乘，不能先在窄整数里溢出再赋给长整型。
易错点总结
- 错误写法：用
double slope = dy / dx当哈希键。反例竖直线[(1,0),(1,1),(1,2)]会除零；不同分数还可能因浮点舍入被误判相等。- 更新条件写成
cnt >= best：后出现的并列直线会覆盖更小下标。反例两条各含 3 点的直线，答案应保留先枚举到的点对。- 叉积使用
int：大坐标差相乘可能溢出后碰巧相等，把不共线点计入。必须在乘法前转long/int64。- 只数斜率相同却不固定锚点：平行线斜率相同但不是同一条线，会被合并成一组。
- 把点对本身忘在计数外：
cnt从 0 开始会使所有候选少算 2，边界 n=2 时甚至得不到有效答案。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 149. 直线上最多的点数 | 困难 | 固定锚点并用归一化斜率计数 |
| 1232. 缀点成线 | 简单 | 单条直线上的叉积判定 |