2021. Brightest Position on Street

English Version

题目描述

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

解法

差分数组 + 排序。

如果用数组实现，空间分配过大。因此可以使用哈希表 + 排序，或者直接使用 TreeMap。

Python3

class Solution:
    def brightestPosition(self, lights: List[List[int]]) -> int:
        d = defaultdict(int)
        for p, r in lights:
            d[p - r] += 1
            d[p + r + 1] -= 1
        s = mx = ans = 0
        for k in sorted(d):
            s += d[k]
            if s > mx:
                mx = s
                ans = k
        return ans

Java

class Solution {
    public int brightestPosition(int[][] lights) {
        TreeMap<Integer, Integer> d = new TreeMap<>();
        for (int[] e : lights) {
            int l = e[0] - e[1], r = e[0] + e[1];
            d.put(l, d.getOrDefault(l, 0) + 1);
            d.put(r + 1, d.getOrDefault(r + 1, 0) - 1);
        }
        int s = 0, mx = 0, ans = 0;
        for (Map.Entry<Integer, Integer> e : d.entrySet()) {
            s += e.getValue();
            if (s > mx) {
                mx = s;
                ans = e.getKey();
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int brightestPosition(vector<vector<int>>& lights) {
        map<int, int> d;
        for (auto& e : lights)
        {
            int l = e[0] - e[1], r = e[0] + e[1];
            ++d[l];
            --d[r + 1];
        }
        int s = 0, mx = 0, ans = 0;
        for (auto& e : d)
        {
            s += e.second;
            if (s > mx)
            {
                mx = s;
                ans = e.first;
            }
        }
        return ans;
    }
};

Go

func brightestPosition(lights [][]int) int {
	d := make(map[int]int)
	for _, e := range lights {
		l, r := e[0]-e[1], e[0]+e[1]
		d[l] += 1
		d[r+1] -= 1
	}

	var keys []int
	for k := range d {
		keys = append(keys, k)
	}
	sort.Ints(keys)

	s, mx, ans := 0, 0, 0
	for _, k := range keys {
		s += d[k]
		if s > mx {
			mx = s
			ans = k
		}
	}
	return ans
}

...