2021. Brightest Position on Street #
Problem #
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 <= 105lights[i].length == 2108 <= positioni <= 1080 <= rangei <= 108
Problem Summary #
A perfectly straight street is represented by a number line. There are street lamps on the street, represented by a 2D array. Each lights[i] = [positioni, rangei] indicates that there is a street lamp at position i, and the lamp can illuminate the area from [positioni - rangei, positioni + rangei] (inclusive). The brightness of position p is defined as the number of street lamps that illuminate position p. Given the street lamps, return the brightest position on the street. If there are multiple brightest positions, return the smallest one.
Solution Approach #
- First calculate the start and end positions of each street lamp. This gives us a collection of coordinate points. Suppose the illuminated range of a lamp is [A, B]. Then on the coordinate axis, add +1 at coordinate point A and -1 at coordinate point B + 1. The meaning of this processing is: coordinate point A can be illuminated by one lamp, so its illumination count increases by one; coordinate point B + 1 is outside the illuminated range of the lamp, so the illumination count decreases by one. Then scan from the beginning of the coordinate axis. Each time we encounter +1, add 1, and each time we encounter -1, subtract 1. In this way, we can calculate the total number of times a certain coordinate point can be illuminated by lamps.
- One thing to note is that the test data given by the problem may include cases where only a single point is illuminated, meaning a lamp illuminates only one coordinate point and its range is 0. The same coordinate point may also be the starting point of multiple lamps. Use a map to deduplicate coordinate points.
Code #
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
}
中文