Hard

题目描述

给你一个数组 points，一个整数 angle 以及你的位置 location，其中 location = [posx, posy] 且 points[i] = [xi, yi] 都表示 X-Y 平面上的整数坐标。

最初，你面向东方进行观测。你不能进行移动，但是可以通过旋转调整观测方向。换句话说，posx 和 posy 不能改变。你的视野范围的角度用 angle 表示，这决定了你观测任意方向时能够看到的角度范围。设 d 为你逆时针旋转的角度，那么你的视野就是角度范围 [d - angle/2, d + angle/2] 所指示的那片区域。

对于每个点，如果由该点、你的位置以及从你的位置直接向东的方向形成的角度位于你的视野中，那么你就可以看到它。

同一个坐标上可以有多个点。在你的位置上也可能有点，无论你的旋转角度是多少，你都能看到在你位置上的点。同时，点不会阻碍你看到其他点。

请返回你能看到的点的最大数目。

示例 1：

输入：points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
输出：3
解释：阴影区域代表你的视野。在你的视野中，所有的点都清晰可见，尽管 [2,2] 和 [3,3] 在同一条直线上，你仍然可以看到 [3,3]。

示例 2：

输入：points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]
输出：4
解释：在你的视野中，所有的点都清晰可见，包括你所在位置上的那个点。

示例 3：

输入：points = [[1,0],[2,1]], angle = 13, location = [1,1]
输出：1

提示：

  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • location.length == 2
  • 0 <= angle < 360
  • 0 <= posx, posy, xi, yi <= 100

解题思路

这道题需要找到在给定视野角度下能看到的最多点数。核心思路是将几何问题转化为滑动窗口问题。

主要思路：

  1. 预处理同位置点：首先统计与观察位置相同的点，这些点无论如何旋转都能看到。

  2. 极角转换：对于其他点，计算它们相对于观察位置的极角（使用 atan2 函数）。这样将二维几何问题转化为一维角度问题。

  3. 排序与双倍数组：将所有角度排序后，为了处理环形特性（0° 和 360° 相邻），将排序后的角度数组复制一份追加到末尾，每个角度加上 2π。

  4. 滑动窗口：使用双指针技术，维护一个角度范围不超过给定 angle 的窗口，找到包含最多点的窗口。

关键技巧：

  • 使用 atan2(y, x) 计算极角，范围是 [-π, π]
  • 将角度转换为度数便于比较
  • 通过双倍数组处理角度的环形特性
  • 滑动窗口找最大值

时间复杂度主要在排序阶段，整体算法高效且准确。

代码实现

class Solution {
public:
    int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
        vector<double> angles;
        int same = 0;
        
        for (auto& point : points) {
            if (point[0] == location[0] && point[1] == location[1]) {
                same++;
            } else {
                angles.push_back(atan2(point[1] - location[1], point[0] - location[0]) * 180.0 / M_PI);
            }
        }
        
        sort(angles.begin(), angles.end());
        
        int n = angles.size();
        for (int i = 0; i < n; i++) {
            angles.push_back(angles[i] + 360.0);
        }
        
        int maxVisible = 0;
        int left = 0;
        
        for (int right = 0; right < angles.size(); right++) {
            while (angles[right] - angles[left] > angle) {
                left++;
            }
            maxVisible = max(maxVisible, right - left + 1);
        }
        
        return maxVisible + same;
    }
};

class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        import math
        
        angles = []
        same = 0
        
        for point in points:
            if point == location:
                same += 1
            else:
                angles.append(math.atan2(point[1] - location[1], point[0] - location[0]) * 180 / math.pi)
        
        angles.sort()
        
        n = len(angles)
        for i in range(n):
            angles.append(angles[i] + 360)
        
        max_visible = 0
        left = 0
        
        for right in range(len(angles)):
            while angles[right] - angles[left] > angle:
                left += 1
            max_visible = max(max_visible, right - left + 1)
        
        return max_visible + same

public class Solution {
    public int VisiblePoints(IList<IList<int>> points, int angle, IList<int> location) {
        List<double> angles = new List<double>();
        int same = 0;
        
        foreach (var point in points) {
            if (point[0] == location[0] && point[1] == location[1]) {
                same++;
            } else {
                angles.Add(Math.Atan2(point[1] - location[1], point[0] - location[0]) * 180.0 / Math.PI);
            }
        }
        
        angles.Sort();
        
        int n = angles.Count;
        for (int i = 0; i < n; i++) {
            angles.Add(angles[i] + 360.0);
        }
        
        int maxVisible = 0;
        int left = 0;
        
        for (int right = 0; right < angles.Count; right++) {
            while (angles[right] - angles[left] > angle) {
                left++;
            }
            maxVisible = Math.Max(maxVisible, right - left + 1);
        }
        
        return maxVisible + same;
    }
}

var visiblePoints = function(points, angle, location) {
    let angles = [];
    let same = 0;
    
    for (let point of points) {
        if (point[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n)主要消耗在排序操作，滑动窗口为 O(n)
空间复杂度O(n)存储角度数组和双倍数组