LeetCode 1232. 缀点成线
目录
题目描述
题意分析
给一组平面上的点，判断它们是否全部落在同一条直线上，返回布尔值。
题目给了两个非常有用的保证：点的数量至少为 2，且所有点两两不同。第一条保证意味着「取前两点确定一条基准直线」这个动作永远合法，不会遇到点数不足的情况；第二条保证意味着前两点必然不重合，它们确定的方向向量不会是零向量，基准直线是良定义的。
坐标是整数，范围 $[-10^4, 10^4]$，点数不超过 1000。全整数输入是最关键的信号——它意味着可以用纯整数运算完成判定，不需要引入除法和浮点数。
需要特别留意的是垂直线的情况：两点横坐标相同时，「斜率」这个概念本身就不存在，任何依赖斜率的表述都必须为它单独开一个分支。这提示我们应该找一个不区分方向的等价判据。
边界：只有两个点（恒为 true）、所有点横坐标相同的竖直线、所有点纵坐标相同的水平线、坐标取到值域两端。
解法：向量叉积判共线
核心思路
用斜率比较会遇到竖直线除零和整数除法截断；浮点数也没有必要。前两个不同点已经确定唯一方向，只需判断其余点相对首点的向量是否与该方向平行。
设基准方向为
(dx, dy) = (x_1 - x_0, y_1 - y_0)，当前点相对首点的向量为(x, y)。两向量平行当且仅当二维叉积为 0，即x × dy = y × dx。这里只做整数乘法，水平线和竖直线无需特判。循环不变量是：处理下标 i 之前，前 i 个点都已被证明位于由前两点确定的直线上。当前点叉积不为 0 时，它就是反例；等于 0 时不变量扩展到下一个点。
正确性说明：前两点不同，因此基准方向不是零向量。叉积为 0 与两个二维向量线性相关等价，所以每个通过检查的点都在同一条基准直线上；若任一点不通过，所有点不可能共线。全部检查通过时返回
true，反之返回false，结论正确。
解题步骤
- 用前两个点计算固定方向
dx、dy。- 从第三个点开始，计算它相对首点的偏移
x、y。- 若
x × dy != y × dx，立即返回false。- 所有点都通过则返回
true；只有两个点时循环为空，结果自然为真。
[[1,2],[2,3],[3,4]]的每个叉积都为 0，因此共线；[[1,1],[2,2],[3,4]]在第三点处叉积不为 0。竖直线[[0,0],[0,1],[0,-1]]同样通过，无需计算无限斜率。代码使用 64 位乘法，使判据不依赖较窄的中间结果范围。
代码实现
class Solution {
public boolean checkStraightLine(int[][] coordinates) {
long x0 = coordinates[0][0];
long y0 = coordinates[0][1];
long dx = coordinates[1][0] - x0;
long dy = coordinates[1][1] - y0;
for (int i = 2; i < coordinates.length; i++) {
long x = coordinates[i][0] - x0;
long y = coordinates[i][1] - y0;
if (x * dy != y * dx) {
return false;
}
}
return true;
}
}
func checkStraightLine(coordinates [][]int) bool {
x0 := int64(coordinates[0][0])
y0 := int64(coordinates[0][1])
dx := int64(coordinates[1][0]) - x0
dy := int64(coordinates[1][1]) - y0
for i := 2; i < len(coordinates); i++ {
x := int64(coordinates[i][0]) - x0
y := int64(coordinates[i][1]) - y0
if x*dy != y*dx {
return false
}
}
return true
}
复杂度分析
- 时间复杂度：$O(n)$。每个点只进行一次常数时间的叉积判断。
- 空间复杂度：$O(1)$。只保存基准点、方向和当前偏移。
关键点总结
- 比较斜率时优先交叉相乘，统一避开除零、截断和浮点表示问题。
- 所有点都相对同一个首点和同一个方向判断，循环状态清晰且互不依赖。
- 前两点不同保证基准方向非零；两点输入天然共线。
- 中间乘法使用 64 位整数，避免先以 32 位相乘再转换时已经溢出。
易错点总结
- 使用整数除法计算斜率：
[[0,0],[2,1],[5,2]]的两个斜率都会截断为 0，错误判为共线；叉积实际为 5 与 4。- 用浮点斜率处理竖直线：
[[0,0],[0,1],[0,-1]]会产生正、负无穷并被判为不同，尽管三点在同一竖线上。- 交叉乘法配对写错：应比较
x × dy与y × dx；写成x × dx == y × dy会把[[0,0],[1,2],[2,4]]误判为不共线。- 只比较斜率绝对值：
[[0,0],[1,1],[1,-1]]的斜率绝对值相同，但第三点不在基准直线上。- 点数为 2 时返回
false：任意两个不同点都能确定一条直线，应自然返回true。- 强转发生在乘法之后：写成
(long) (x * dy)时，若 x、dy 是int，溢出已在转换前发生；应先让参与运算的变量成为 64 位。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 149. 直线上最多的点数 | 困难 | 基准点不固定要逐个枚举，方向需约分成最简分数当哈希键 |
| 593. 有效的正方形 | 中等 | 判据从平行换成距离，用六条边长的多重集合避免枚举顺序 |
| 812. 最大三角形面积 | 简单 | 叉积不再判零而是取绝对值的一半当面积，直接复用同一式子 |
| 836. 矩形重叠 | 简单 | 判据从共线换成区间相交，用「不相交取反」避开分类讨论 |