1610. 可见点的最大数目

exiaohu 于 2021-12-16 发布

题目链接：1610. 可见点的最大数目

思路很简单：

  1. 首先计算出每个点相对 location 的角度，该角度在$[0, 360)$ 之间；

  2. 其中特殊处理和 location 重合的点，这些点的角度为任意；

  3. 然后使用滑动窗口，找到窗口大小为 angle 的，其中容纳的点最多的一个窗口即可；

  4. 需要注意的是，角度是循环的，可以通过将原始 angles 数组向右映射，解决角度循环的问题。

from typing import List
import math


class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        x0, y0 = location
        points, sames = filter(lambda item: item[0] != x0 or item[1] != y0, points), filter(
            lambda item: item[0] == x0 and item[1] == y0, points)
        angles = sorted(map(lambda item: math.atan2(item[1] - y0, item[0] - x0) / math.pi * 180 + 180, points))

        l, r, ans, len_angles = 0, 0, 0, len(angles)

        angles = angles + list(map(lambda al: al + 360, angles))

        while l < len_angles:
            while r < len(angles) and angles[r] <= angles[l] + angle:
                r += 1
            ans = max(ans, r - l)
            l += 1

        return ans + len(list(sames))