Question

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

English Version

题目描述

给你一个整数 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，因为没有位置满足亮度要求。

 

提示:

• 1 <= n <= 105
• 1 <= lights.length <= 105
• 0 <= positioni < n
• 0 <= rangei <= 105
• requirement.length == n
• 0 <= requirement[i] <= 105

解法

方法一：差分数组

时间复杂度 $O(n)$。

class Solution:
  def meetRequirement(
    self, n: int, lights: List[List[int]], requirement: List[int]
  ) -> int:
    d = [0] * 100010
    for p, r in lights:
      i, j = max(0, p - r), min(n - 1, p + r)
      d[i] += 1
      d[j + 1] -= 1
    return sum(s >= r for s, r in zip(accumulate(d), requirement))

class Solution {
  public int meetRequirement(int n, int[][] lights, int[] requirement) {
    int[] d = new int[100010];
    for (int[] e : lights) {
      int i = Math.max(0, e[0] - e[1]);
      int j = Math.min(n - 1, e[0] + e[1]);
      ++d[i];
      --d[j + 1];
    }
    int s = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      s += d[i];
      if (s >= requirement[i]) {
        ++ans;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int meetRequirement(int n, vector<vector<int>>& lights, vector<int>& requirement) {
    vector<int> d(100010);
    for (auto& e : lights) {
      int i = max(0, e[0] - e[1]), j = min(n - 1, e[0] + e[1]);
      ++d[i];
      --d[j + 1];
    }
    int s = 0, ans = 0;
    for (int i = 0; i < n; ++i) {
      s += d[i];
      if (s >= requirement[i]) ++ans;
    }
    return ans;
  }
};

func meetRequirement(n int, lights [][]int, requirement []int) int {
  d := make([]int, 100010)
  for _, e := range lights {
    i, j := max(0, e[0]-e[1]), min(n-1, e[0]+e[1])
    d[i]++
    d[j+1]--
  }
  var s, ans int
  for i, r := range requirement {
    s += d[i]
    if s >= r {
      ans++
    }
  }
  return ans
}