python-leetcode-直线上最多的点数

149. 直线上最多的点数 - 力扣（LeetCode）

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 2:
            return n
        
        max_points = 0
        
        for i in range(n):
            slope_count = defaultdict(int)
            duplicates = 0
            verticals = 0
            local_max = 0
            
            for j in range(n):
                if i == j:
                    continue
                
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]
                
                if dx == 0 and dy == 0:
                    # 重叠点
                    duplicates += 1
                elif dx == 0:
                    # 垂直线
                    verticals += 1
                else:
                    # 化简斜率
                    g = gcd(dx, dy)
                    dx //= g
                    dy //= g
                    
                    # 保证唯一表示，dx 为正数
                    if dx < 0:
                        dx = -dx
                        dy = -dy
                    
                    # 使用元组作为哈希表的键
                    slope_count[(dx, dy)] += 1
                    local_max = max(local_max, slope_count[(dx, dy)])
            
            max_points = max(max_points, max(local_max, verticals) + duplicates + 1)
        
        return max_points