LeetCode 1610. 可见点的最大数目

Categories:

题目描述
思路分析
1. 解法一：极角排序 + 滑动窗口（推荐）
相似题目

题目描述

✅ 1610. 可见点的最大数目

思路分析

解法一：极角排序 + 滑动窗口（推荐）

核心思路：

将所有点（除与人重合的点）转换为相对于人位置的极角（使用 atan2）

在同一位置的点单独统计，最终结果都加上

将极角数组复制一份并偏移 360°（2π），拼接成长度 2n 的数组，以处理角度环绕问题

排序后用滑动窗口，维护角度差不超过 angle 的最大点数

答案 = 滑动窗口最大值 + 与人重合的点数

复杂度分析：

时间复杂度：O(n log n)，其中 n 为点的数量，主要为排序耗时

空间复杂度：O(n)，存储极角数组

class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        int lx = location.get(0);
        int ly = location.get(1);

        // 与人重合的点单独统计
        int samePos = 0;
        List<Double> angles = new ArrayList<>();

        for (List<Integer> point : points) {
            int dx = point.get(0) - lx;
            int dy = point.get(1) - ly;

            if (dx == 0 && dy == 0) {
                samePos++;
                continue;
            }

            // 转换为角度（-180 ~ 180）
            angles.add(Math.toDegrees(Math.atan2(dy, dx)));
        }

        Collections.sort(angles);

        int n = angles.size();

        // 复制一份并偏移 360°，处理环绕
        for (int i = 0; i < n; i++) {
            angles.add(angles.get(i) + 360.0);
        }

        int maxVisible = 0;
        int left = 0;

        // 滑动窗口：维护角度差不超过 angle 的最大点数
        for (int right = 0; right < angles.size(); right++) {
            while (angles.get(right) - angles.get(left) > angle) {
                left++;
            }
            maxVisible = Math.max(maxVisible, right - left + 1);
        }

        return maxVisible + samePos;
    }
}

func visiblePoints(points [][]int, angle int, location []int) int {
    lx, ly := location[0], location[1]

    // 与人重合的点单独统计
    samePos := 0
    var angles []float64

    for _, point := range points {
        dx := point[0] - lx
        dy := point[1] - ly

        if dx == 0 && dy == 0 {
            samePos++
            continue
        }

        // 转换为角度（-180 ~ 180）
        deg := math.Atan2(float64(dy), float64(dx)) * 180 / math.Pi
        angles = append(angles, deg)
    }

    sort.Float64s(angles)

    n := len(angles)

    // 复制一份并偏移 360°，处理环绕
    for i := 0; i < n; i++ {
        angles = append(angles, angles[i]+360.0)
    }

    maxVisible := 0
    left := 0

    // 滑动窗口：维护角度差不超过 angle 的最大点数
    for right := 0; right < len(angles); right++ {
        for angles[right]-angles[left] > float64(angle) {
            left++
        }
        if right-left+1 > maxVisible {
            maxVisible = right - left + 1
        }
    }

    return maxVisible + samePos
}

相似题目

题目	难度	考察点
478. 在圆内随机生成点	中等	几何、数学
587. 安装栅栏	困难	凸包、几何
1453. 圆形靶内的最大飞镖数量	困难	几何
149. 直线上最多的点数	困难	几何、哈希表
356. 直线镜像	中等	哈希表、数学
469. 凸多边形	中等	几何、数学

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/96846428