列表

详情

2237. 计算街道上满足所需亮度的位置数量

给你一个整数 n。一条完全笔直的街道用一条从 0 到 n - 1 的数轴表示。给你一个二维整数数组 lights，表示街道上的路灯。每个 lights[i] = [positioni, rangei] 表示在位置 positioni 有一盏路灯，从 [max(0, positioni - rangei), min(n - 1, positioni + rangei)] (包含边界) 开始照亮该区域。

位置 p 的 亮度 定义为点亮位置 p 的路灯的数量。给定一个大小为 n 的整数数组 requirement，数组的 下标从 0 开始，其中 requirement[i] 是街道上第 i 个位置的最小 亮度。

返回街道上 0 到 n - 1 之间 亮度至少满足 requirement[i] 的位置 i 的数量。

 

示例 1:

输入: n = 5, lights = [[0,1],[2,1],[3,2]], requirement = [0,2,1,4,1]
输出: 4
解释:
- 第一盏路灯照亮区域范围为 [max(0,0 - 1)， min(n - 1,0 + 1)] =[0,1](含边界)。
- 第二盏路灯的点亮范围为 [max(0,2 - 1)， min(n - 1,2 + 1)] =[1,3](含边界)。
- 第三盏路灯照亮区域范围为 [max(0,3 - 2)， min(n - 1,3 + 2)] =[1,4](含边界)。

- 位置 0 被第一盏路灯覆盖。它被 1 个路灯覆盖，大于 requirement[0]。
- 位置 1 被第一、第二和第三个路灯覆盖。被 3 个路灯覆盖，大于 requirement[1]。
- 位置 2 由第二和第三路灯覆盖。被 2 个路灯覆盖，大于 requirement[2]。
- 位置 3 由第二和第三路灯覆盖。它被 2 个路灯覆盖，比 requirement[3] 少。
- 位置 4 被第三个路灯覆盖。它被 1 盏路灯覆盖，等于 requirement[4]。

位置 0、1、2、4 满足要求，因此返回4。

示例 2:

输入: n = 1, lights = [[0,1]], requirement = [2]
输出: 0
解释:
- 第一盏路灯照亮区域范围为 [max(0,0 - 1)， min(n - 1,0 + 1)] =[0,0](含边界)。
- 位置 0 被第一盏路灯覆盖。它被 1 个路灯覆盖，比 requirement[0] 少。
- 返回0，因为没有位置满足亮度要求。

 

提示:

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int meetRequirement(int n, vector<vector<int>>& lights, vector<int>& requirement) { } };

cpp 解法, 执行用时: 256 ms, 内存消耗: 124 MB, 提交时间: 2023-10-17 20:35:34 

class Solution {
public:
    int meetRequirement(int n, vector<vector<int>>& lights, vector<int>& requirement) {
        int diff[n+1];
        memset(diff, 0, sizeof(diff));
        for (vector<int>& l : lights)
        {
            ++diff[max(0, l[0]-l[1])];
            --diff[min(n, l[0]+l[1]+1)];
            // cout << max(0, l[0]-l[1]) << " " << min(n, l[0]+l[1]+1) << endl;
        }

        int res = 0;
        // 目前累计的数量快速比较
        long long curr = 0;
        for (int i = 0; i < n; ++i)
        {
            curr += diff[i];
            // cout << curr << " " << requirement[i] << endl;
            res += requirement[i] <= curr;
        }

        return res;
    }
};

java 解法, 执行用时: 194 ms, 内存消耗: 79.3 MB, 提交时间: 2023-10-17 20:35:13 

class Solution {
    public int meetRequirement(int n, int[][] lights, int[] requirement) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(Integer.MIN_VALUE, 0);
        for (int[] light : lights) {
            int left = light[0] - light[1];
            int right  = light[0] + light[1];
            map.put(left, map.getOrDefault(left, 0) + 1);
            map.put(right + 1, map.getOrDefault(right + 1, 0) - 1);
        }

        int sum = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            sum += entry.getValue();
            entry.setValue(sum);
        }
        int count = 0;
        for (int i = 0; i < requirement.length; i++) {
            int light = requirement[i];
            if (map.floorEntry(i).getValue() >= light) {
                count++;
            }
        }
        return count;
    }
}

golang 解法, 执行用时: 204 ms, 内存消耗: 20.7 MB, 提交时间: 2023-10-17 20:34:58 

func meetRequirement(n int, lights [][]int, requirement []int) int {
	preSum:= make([]int, n)
	for i := 0; i < len(lights); i++ {
		start:= lights[i][0]-lights[i][1]
		if start <0{
			start = 0
		}
		preSum[start]++
		end:= lights[i][0]+lights[i][1]+1
		if end <n{
			preSum[end]--
		}
	}
    
	ans:=0
	for i := 0; i < n; i++ {
        if i >0{
            preSum[i]+=preSum[i-1]
        }
		
		if preSum[i] >= requirement[i]{
			ans++
		}
	}
    // fmt.Println(preSum)
	return ans
	
}

python3 解法, 执行用时: 220 ms, 内存消耗: 39 MB, 提交时间: 2023-10-17 20:34:25 

class Solution:
    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:
        diff = [0] * (n + 1)
        for p, r in lights:
            diff[max(0, p - r)] += 1
            diff[min(n, p + r + 1)] -= 1
        ans = cur = 0
        for r, d in zip(requirement, diff):
            cur += d
            ans += int(cur >= r)
        return ans

上一题

© 2024 leetcode.cn