LeetCode 1610. 可见点的最大数目

2023-04-17 HGNULB 约 6 分钟

文章信息 6 个分类 · 5 个标签

分类

LeetCode CodeTop 困难 未解决 1-2 阿里

标签

数组 数学 排序 滑动窗口 几何

题目描述

✅ 1610. 可见点的最大数目

题意分析

观察者的位置固定，可以任意旋转一个宽度为 angle 的视野，求最多能同时看见多少个点。视野边界上的点也算可见，点之间不会互相遮挡，所以距离远近不影响答案。

同一个坐标可以有多条点记录，都要分别计数；与观察者重合的点在任何朝向下都可见。其余点只需要考虑相对观察者的方向。

解法：极角排序 + 滑动窗口

核心思路

[!blue]

先把与观察者重合的点计入 same，其他点用 atan2(dy, dx) 转成极角。它同时考虑横纵坐标的符号，能区分全部象限；同方向的多个点保留多个角度记录，不去重。

将角度排序后，一个朝向下可见的方向在圆周上必然是连续一段。反过来，只要一段方向的最大跨度不超过视角，就一定能把视野旋转到覆盖它。因此问题转为寻找跨度受限的最长连续段。

圆周存在首尾边界，接近最小角度和最大角度的点也可能相邻。把排好序的角度复制一份，每项加 2π 后接到原数组末尾，就把跨边界的视野展开成直线上的普通区间。题目视角小于一整周，两份角度已经能表示全部可能的圆周区间。

用左右指针维护窗口，右端逐个扩展。当首尾角度差超过视角，或窗口点数超过原有方向点数 m 时，持续右移左端。排序后扩展右端不会减小跨度，移动左端不会增大跨度，首次恢复合法时就是当前右端下的最长合法窗口。

atan2 返回弧度，需要把输入角度也转换成弧度再比较。边界本应包含在视野内，代码加入很小的误差容忍，避免浮点舍入把恰好在边界上的点排除。窗口最大长度最后加上始终可见的 same。

解题步骤

1. 计算每个点相对观察者的坐标差，重合点单独计数，其余点转换为方向角。
2. 对方向角排序。若没有非重合点，直接返回 same。
3. 创建长度为 2m 的数组，前半保存原角度，后半保存原角度加 2π。
4. 将 angle 从角度制转为弧度，扫描右端点；窗口跨度超限或数量超过 m 时收缩左端。
5. 每次恢复合法后更新最大窗口长度，最后加上重合点数量返回。

代码实现

class Solution {
    private static final double EPSILON = 1e-12;

    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        List<Double> directions = new ArrayList<>();
        int same = 0;

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

            // 同位置点始终可见，不参与方向窗口。
            if (dx == 0 && dy == 0) {
                same++;
            } else {
                directions.add(Math.atan2(dy, dx));
            }
        }

        Collections.sort(directions);
        int m = directions.size();

        if (m == 0) {
            return same;
        }

        // 复制并加一周，将跨越角度边界的窗口展开到直线上。
        double[] extended = new double[2 * m];

        for (int i = 0; i < m; i++) {
            extended[i] = directions.get(i);
            extended[i + m] = directions.get(i) + 2 * Math.PI;
        }

        double limit = Math.toRadians(angle);
        int left = 0;
        int best = 0;

        for (int right = 0; right < extended.length; right++) {
            // 收缩到合法视角，同时不让窗口超过原方向点数。
            while (right - left + 1 > m || extended[right] - extended[left] > limit + EPSILON) {
                left++;
            }

            best = Math.max(best, right - left + 1);
        }

        return best + same;
    }
}

import (
    "math"
    "sort"
)

const epsilon = 1e-12

func visiblePoints(points [][]int, angle int, location []int) int {
    directions := make([]float64, 0, len(points))
    same := 0
    for _, point := range points {
        dx := point[0] - location[0]
        dy := point[1] - location[1]
        // 同位置点始终可见，不参与方向窗口。
        if dx == 0 && dy == 0 {
            same++
        } else {
            directions = append(directions, math.Atan2(float64(dy), float64(dx)))
        }
    }

    sort.Float64s(directions)
    m := len(directions)
    if m == 0 {
        return same
    }

    // 复制并加一周，将跨越角度边界的窗口展开到直线上。
    extended := make([]float64, 2*m)
    for i, direction := range directions {
        extended[i] = direction
        extended[i+m] = direction + 2*math.Pi
    }

    limit := float64(angle) * math.Pi / 180
    left, best := 0, 0
    for right := range extended {
        // 收缩到合法视角，同时不让窗口超过原方向点数。
        for right-left+1 > m || extended[right]-extended[left] > limit+epsilon {
            left++
        }
        if right-left+1 > best {
            best = right - left + 1
        }
    }
    return best + same
}

复杂度分析

• 时间复杂度：$O(n\log(n+1))$，排序占主导，窗口线性移动。
• 空间复杂度：$O(n)$，保存方向和扩展数组。

关键点总结

[!green]

• 位置重合的点不受方向限制，其余点只按方向判断可见性。
• 排序把视野内的点变成连续区间，复制并加一周处理跨越首尾的区间。
• 窗口最多包含 m 个原始方向记录，扩展数组中的复制项不能让同一个点重复贡献。
• 左右指针只向前移动，排序后的窗口扫描为线性时间。

易错点总结

[!yellow]

• 不能把重合点当作方向零，否则它们会被错误地限制在某些朝向内。
• 不能按角度或坐标去重，同位置、同方向的不同点记录都应保留计数。
• 只扫描原角度数组会漏掉跨首尾边界的视野；复制后仍要限制原始点的计数范围。
• atan(dy / dx) 不能区分全部象限，竖直方向还可能除零，应使用 atan2(dy, dx)。
• 比较双方必须使用相同角度单位，并保留闭区间边界及必要的浮点误差容忍。

相似题目

题目	难度	关联与区别
539. 最小时间差	中等	同样处理周期边界，可把排序后的角度复制并加一周，再在线性序列中处理跨零方向的窗口。

转载与许可

作者 HGNULB

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

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！