LeetCode 1610. 可见点的最大数目

2023-04-17 HGNULB 约 7 分钟

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

分类

题目描述

✅ 1610. 可见点的最大数目

题意分析

你站在平面上的固定位置 location，视野是一个张角为 angle 度的扇形，可以原地旋转但不能移动。给定一堆点的坐标，问旋转到最佳朝向时最多能同时看到多少个点。

有三条规则必须先咬清楚。第一，位置固定不可移动，所以每个点相对于你的方向是确定的、只需算一次。第二，视野边界算「看得见」，也就是恰好落在扇形两条边上的点也计入，判定要用闭区间。第三，与你重合的点（dx 和 dy 都为 0）无论朝哪个方向都能看见，必须单独统计并无条件加进答案——它们根本没有方向可言，硬要算角度会得到无意义的值。

既然距离完全不影响可见性，每个点就退化成一个方向值。问题随之变成：在一圈方向里，找一个宽度为 angle 的区间，让落在其中的方向最多。

点数上限是 $10^5$，angle 是 0 到 360 的整数。$10^5$ 的规模允许排序（$O(n \log n)$），但不允许对每个点都做一次 $O(n)$ 的统计。

最大的陷阱是「一圈」这个词：方向是环形的，359 度和 1 度只差 2 度而不是 358 度。任何把方向当成一条直线来处理的写法，都会漏掉跨越 0 度的那些窗口。

边界上，angle = 0 时视野退化成一条射线，只能看到方向完全相同的那些点（外加重合点）；所有点都与你重合时答案就是点数本身。

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

核心思路

与观察者同坐标的点没有方向限制，无论朝向如何都可见，应单独计入 same；其余点只需保留相对观察位置的极角 atan2(dy, dx)。

排序后，某个视野方向能覆盖的点必然是角度序列中的一段连续区间，区间最大跨度不超过给定视角。难点是角度首尾相接：接近 -π 与 π 的方向在几何上相邻。把排序后的角度复制一份并全部加 2π，圆环窗口就变成普通线性窗口。

使用左右指针维护窗口。当角度差超过视角，或窗口长度超过方向点总数时移动左端；后一个条件保证每个点的两份副本不会同时被计入。

窗口不变量：每轮收缩后，窗口内角度跨度不超过视角、包含的每个原始点至多一次，并且对当前右端点而言左端点尽可能靠左。

正确性：任意观察方向对应圆周上一段给定长度的闭区间；复制角度后，这段区间总能表示成扩展数组中的连续窗口。滑动窗口对每个右端点保留最大的合法窗口，因此枚举到全局最多的方向点。最后加上始终可见的 same 即为答案。

浮点比较使用很小的 epsilon，把理论上恰好落在视野边界的点计入，避免 atan2 与角度换算的舍入误差造成误删。

解题步骤

遍历所有点；同坐标点计入 same，其余点用 atan2 转成极角。

将极角升序排序，并构造长度两倍的数组，后一半等于前一半加 2π。

右指针逐个扩展；若角度跨度大于视角加误差容忍，或窗口包含超过原方向点数，则移动左指针。

记录最大合法窗口长度，返回它与 same 之和。

样例 points = [[2,1],[2,2],[3,3]]、location = [1,1]、angle = 90 中，三个方向角都落在同一个 90 度窗口内，答案为 3。

同坐标点不能送入 atan2(0,0)；angle = 0 时同一射线上的多个点仍可同时看见；跨越角度边界的窗口由复制数组处理；若所有点都与观察者重合，角度数组为空，答案直接是 same。

代码实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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)$，极角排序占主导；滑动窗口为 $O(n)$。

空间复杂度：$O(n)$，用于方向角及其扩展数组；同坐标点不进入数组。

关键点总结

同位置点始终可见，必须与有方向的点分开统计。

极角排序把二维方向问题转成一维连续窗口。

复制角度并加 2π 用于线性化跨圆周边界的窗口。

窗口最多包含 m 个方向点，避免重复副本被同时计数。

闭区间边界需要小量浮点容忍，但不能使用过大的误差掩盖真实越界。

易错点总结

把同坐标点计算为角度 0：它们会错误地只在朝向 0 时可见，而实际始终可见。

只扫描原角度数组：会漏掉跨越 -π 与 π 的最优窗口。

复制后不限制窗口长度：视角接近整圆时可能同时计入同一点的两份副本。

用严格浮点边界直接排除：理论上恰好位于边界的点可能因舍入误差被误删。

使用 atan(dy / dx)：无法区分象限，并在 dx = 0 时出错；应使用 atan2。

相似题目

题目	难度	考察点
209. 长度最小的子数组	中等	变长滑窗的最简形态，收缩条件由区间和而非跨度决定
1004. 最大连续1的个数 III	中等	窗口合法性由「可翻转次数」约束，同为「先收缩后更新」的骨架
424. 替换后的最长重复字符	中等	窗口内要维护众数计数，判定量比本题的跨度差复杂
1456. 定长子串中元音的最大数目	中等	定长窗口无需收缩，适合对比定长与变长两种滑窗写法
239. 滑动窗口最大值	困难	窗口内需维护单调队列，考察的是窗口状态而非窗口长度
149. 直线上最多的点数	困难	同样把点对转成方向（斜率）再分组统计，但要处理垂直线与精度问题
1052. 爱生气的书店老板	中等	定长窗口求最大增益，答案由固定部分加窗口部分组成，结构与本题的「重合点 + 窗口」相似