2021. Brightest Position on Street

English Version

题目描述

一条街上有很多的路灯，路灯的坐标由数组 lights 的形式给出。 每个 lights[i] = [positioni, rangei] 代表坐标为 positioni 的路灯照亮的范围为 [positioni - rangei, positioni + rangei] （包括顶点）。

位置 p 的亮度由能够照到 p的路灯的数量来决定的。

给出 lights, 返回最亮的位置 。如果有很多，返回坐标最小的。

 

示例 1:

输入: lights = [[-3,2],[1,2],[3,3]]
输出: -1
解释:
第一个路灯照亮的范围是[(-3) - 2, (-3) + 2] = [-5, -1].
第二个路灯照亮的范围是 [1 - 2, 1 + 2] = [-1, 3].
第三个路灯照亮的范围是 [3 - 3, 3 + 3] = [0, 6].
坐标-1 被第一个和第二个路灯照亮，亮度为 2
坐标 0，1，2 都被第二个和第三个路灯照亮，亮度为 2.
对于以上坐标，-1 最小，所以返回-1

示例 2：

输入: lights = [[1,0],[0,1]]
输出: 1

示例 3：

输入: lights = [[1,2]]
输出: -1

 

提示:

• 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
}

...