1610.可见点的最大数目.md

1610.可见点的最大数目

/*
 * @lc app=leetcode.cn id=1610 lang=typescript
 *
 * [1610] 可见点的最大数目
 */

// @lc code=start
function visiblePoints(points: [number, number][], angle: number, location: [number, number]): number {}
// @lc code=end

解法 1: 排序+前缀和+二分

计算每个点相对 location 的极角,然后按照极角从小到达排序,统计每个点的前缀和,遍历每个坐标,统计以当前极角为视野的上界时,能看到的点的数量,记录最大值返回.

function visiblePoints(points: [number, number][], angle: number, location: [number, number]): number {
  const getAngle = ([x1, y1]: [number, number], [x2, y2]: [number, number]) =>
    ((Math.atan2(y2 - y1, x2 - x1) * 180) / Math.PI + 360) % 360

  let newpoints = points.filter(([x, y]) => !(location[0] === x && location[1] === y))
  // 统计和 location 相通的点,这些点总是能被看到
  let base = points.length - newpoints.length

  // 按照角度大小进行排序
  newpoints.sort((a, b) => getAngle(location, a) - getAngle(location, b))
  const sums: number[] = []
  const angles: number[] = []
  // 统计前缀和,将相通角度的点合并
  for (let i = 0; i < newpoints.length; i++) {
    const curAngle = getAngle(location, newpoints[i])
    angles.push(curAngle)
    sums.push((sums[sums.length - 1] ?? 0) + 1)
    while (i < newpoints.length - 1 && curAngle === getAngle(location, newpoints[i + 1])) {
      sums[sums.length - 1]++
      i++
    }
  }

  // 通过二分搜索,查找一个角度的索引
  const getIndex = (angle: number) => {
    let left = 0,
      right = angles.length
    while (left < right) {
      const mid = (left + right) >> 1
      if (angles[mid] < angle) {
        left = mid + 1
      } else {
        right = mid
      }
    }
    return right
  }

  let res = 0
  for (let i = 0; i < angles.length; i++) {
    let min = getIndex(Math.max(angles[i] - angle, 0))
    let sum = 0
    sum = sums[i] - (sums[min - 1] ?? 0)
    // 如果当前点的极角小于 angle 说明视野超过了 0,需要再加上小于角度 0 时能看到的点
    if (angles[i] < angle) {
      min = getIndex(angles[i] - angle + 360)
      sum += sums[angles.length - 1] - (sums[min - 1] ?? 0)
    }
    res = Math.max(res, sum)
  }
  return res + base
}

优化

可以直接用两个点的索引相减来求得范围内的点的数量,省去统计前缀和的代码,让代码更简介

function visiblePoints(points: [number, number][], angle: number, location: [number, number]): number {
  const getAngle = ([x1, y1]: [number, number], [x2, y2]: [number, number]) =>
    ((Math.atan2(y2 - y1, x2 - x1) * 180) / Math.PI + 360) % 360

  let angles = points.filter(([x, y]) => !(location[0] === x && location[1] === y)).map(pos => getAngle(location, pos))

  angles.sort((a, b) => a - b)

  let base = points.length - angles.length

  const getIndex = (angle: number) => {
    let [left, right] = [0, angles.length]
    while (left < right) {
      const mid = (left + right) >> 1
      if (angles[mid] < angle) left = mid + 1
      else right = mid
    }
    return right
  }

  let res = 0
  for (let i = 0; i < angles.length; i++) {
    if (angles[i] === angles[i + 1]) continue
    let min = getIndex(Math.max(angles[i] - angle, 0))
    let sum = i - (min - 1)
    if (angles[i] < angle) {
      min = getIndex(angles[i] - angle + 360)
      sum += angles.length - min
    }
    res = Math.max(res, sum)
  }
  return res + base
}

Case

test.each([
  {
    input: {
      points: [
        [2, 1],
        [2, 2],
        [3, 3],
      ],
      angle: 90,
      location: [1, 1],
    },
    output: 3,
  },
  {
    input: {
      points: [
        [2, 1],
        [2, 2],
        [3, 4],
        [1, 1],
      ],
      angle: 90,
      location: [1, 1],
    },
    output: 4,
  },
  {
    input: {
      points: [
        [1, 0],
        [2, 1],
      ],
      angle: 13,
      location: [1, 1],
    },
    output: 1,
  },
])(
  'input: points = $input.points, angle = $input.angle, location = $input.location',
  ({ input: { points, angle, location }, output }) => {
    expect(visiblePoints(points, angle, location)).toEqual(output)
  },
)