2021. Brightest Position on Street

2021. Brightest Position on Street#

题目 #

A perfectly straight street is represented by a number line. The street has street lamp(s) on it and is represented by a 2D integer array `lights`. Each `lights[i] = [positioni, rangei]` indicates that there is a street lamp at position `positioni` that lights up the area from `[positioni - rangei, positioni + rangei]` (inclusive).

The brightness of a position `p` is defined as the number of street lamp that light up the position `p`.

Given `lights`, return the brightest position on the street. If there are multiple brightest positions, return the smallest one.

Example 1:

``````Input: lights = [[-3,2],[1,2],[3,3]]
Output: -1
Explanation:
The first street lamp lights up the area from [(-3) - 2, (-3) + 2] = [-5, -1].
The second street lamp lights up the area from [1 - 2, 1 + 2] = [-1, 3].
The third street lamp lights up the area from [3 - 3, 3 + 3] = [0, 6].

Position -1 has a brightness of 2, illuminated by the first and second street light.
Positions 0, 1, 2, and 3 have a brightness of 2, illuminated by the second and third street light.
Out of all these positions, -1 is the smallest, so return it.

``````

Example 2:

``````Input: lights = [[1,0],[0,1]]
Output: 1
Explanation:
The first street lamp lights up the area from [1 - 0, 1 + 0] = [1, 1].
The second street lamp lights up the area from [0 - 1, 0 + 1] = [-1, 1].

Position 1 has a brightness of 2, illuminated by the first and second street light.
Return 1 because it is the brightest position on the street.

``````

Example 3:

``````Input: lights = [[1,2]]
Output: -1
Explanation:
The first street lamp lights up the area from [1 - 2, 1 + 2] = [-1, 3].

Positions -1, 0, 1, 2, and 3 have a brightness of 1, illuminated by the first street light.
Out of all these positions, -1 is the smallest, so return it.

``````

Constraints:

• `1 <= lights.length <= 105`
• `lights[i].length == 2`
• `108 <= positioni <= 108`
• `0 <= rangei <= 108`

解题思路 #

• 先将每个路灯的起始和终点位置计算出来。这样我们得到了一堆坐标点。假设灯照亮的范围是 [A, B]，那么在坐标轴上 A 坐标点处 + 1， B + 1 坐标点处 -1 。这样处理的含义是：坐标点 A 可以被一盏灯照亮，所以它照亮次数加一，坐标点 B + 1 出了灯照亮的范围了，所以照亮次数减一。那么从坐标轴坐标开始扫一遍，每次遇到 + 1 的时候就 + 1，遇到 - 1 的地方就 - 1。如此可以算出某个坐标点处，可以被灯照亮的总次数。
• 需要注意的点是，题目给的测试数据可能会有单点照亮的情况，即某一盏灯只照亮一个坐标点，灯照范围为 0。同一个坐标点也可能是多个灯的起点。用一个 map 去重坐标点即可。

代码 #

``````package leetcode

import (
"sort"
)

type lightItem struct {
index int
sign  int
}

func brightestPosition(lights [][]int) int {
lightMap, lightItems := map[int]int{}, []lightItem{}
for _, light := range lights {
lightMap[light[0]-light[1]] += 1
lightMap[light[0]+light[1]+1] -= 1
}
for k, v := range lightMap {
lightItems = append(lightItems, lightItem{index: k, sign: v})
}
sort.SliceStable(lightItems, func(i, j int) bool {
return lightItems[i].index < lightItems[j].index
})
res, border, tmp := 0, 0, 0
for _, v := range lightItems {
tmp += v.sign
if border < tmp {
res = v.index
border = tmp
}
}
return res
}
``````

Apr 8, 2023