149. Max Points on a Line

Hard

Description

給定一組二維平面上的點 points，找出最多有多少個點在同一條直線上。

Example:

Input: points = [[1,1],[2,2],[3,3]] Output: 3

Intuition#

核心思路：固定一個點，用斜率分組其他點，找出同斜率最多的點數。

兩點確定一條直線，三個以上的點共線意味著任兩點間的斜率相同
固定一個點 i，計算它與其他所有點的斜率，用 HashMap 計數
斜率用分數（約分後的 dy/dx）表示，避免浮點數精度問題
需要特別處理垂直線（dx=0）和水平線（dy=0）

Approaches#

1: 暴力三重迴圈#

概念: 枚舉所有三點組合，檢查是否共線
時間複雜度: O(n^3) - 三重迴圈
空間複雜度: O(1)

class Solution {
    fun maxPoints(points: Array<IntArray>): Int {
        val n = points.size
        if (n <= 2) return n
        var result = 2
        for (i in 0 until n) {
            for (j in i + 1 until n) {
                var count = 2
                for (k in j + 1 until n) {
                    // 用叉積判斷共線：(y2-y1)(x3-x1) == (y3-y1)(x2-x1)
                    val cross = (points[j][1] - points[i][1]).toLong() *
                                (points[k][0] - points[i][0]) -
                                (points[k][1] - points[i][1]).toLong() *
                                (points[j][0] - points[i][0])
                    if (cross == 0L) count++
                }
                result = maxOf(result, count)
            }
        }
        return result
    }
}

⭐2: HashMap 斜率分組#

概念: 固定每個點，用約分後的斜率作為 key 分組，找出最大共線數
時間複雜度: O(n^2) - 兩層迴圈
空間複雜度: O(n) - HashMap

class Solution {
    fun maxPoints(points: Array<IntArray>): Int {
        val n = points.size
        if (n <= 2) return n
        var result = 2

        for (i in 0 until n) {
            val slopeMap = HashMap<String, Int>()
            for (j in i + 1 until n) {
                var dy = points[j][1] - points[i][1]
                var dx = points[j][0] - points[i][0]

                // 約分
                val g = gcd(Math.abs(dy), Math.abs(dx))
                if (g != 0) {
                    dy /= g
                    dx /= g
                }

                // 統一符號：讓 dx 為正，或 dx=0 時讓 dy 為正
                if (dx < 0) {
                    dx = -dx
                    dy = -dy
                } else if (dx == 0) {
                    dy = Math.abs(dy)
                }

                val key = "$dy/$dx"
                slopeMap[key] = (slopeMap[key] ?: 0) + 1
            }

            for (count in slopeMap.values) {
                result = maxOf(result, count + 1) // +1 包含點 i 自己
            }
        }
        return result
    }

    private fun gcd(a: Int, b: Int): Int {
        return if (b == 0) a else gcd(b, a % b)
    }
}

🔑 Takeaways#

Pattern: 固定一個元素 + HashMap 分組是處理「共性」問題的常見手法
關鍵技巧: 用約分後的分數表示斜率避免浮點精度問題；用叉積判斷共線也是常用替代方案