难度: Medium
Submission
运行时间: 157 ms
内存: 41.9 MB
class Solution:
def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:
pre = [0] * (n + 1)
for x, pos in lights:
l, r = max(0, x-pos), min(n-1, x+pos) + 1
pre[l] += 1
pre[r] -= 1
count = list(accumulate(pre))
# print(count)
result = 0
for x, y in zip(count, requirement):
if x >= y:
result += 1
return result
Explain
该题解采用了差分数组的方法来有效地计算街道上各位置的亮度。首先，对于每个灯光的位置和范围，计算该灯光能照亮的最左边界和最右边界+1的位置，并在差分数组pre中对应位置进行加1和减1操作。这样设置后，通过累加差分数组，我们可以得到每个位置的实际亮度。最后，通过比较每个位置的实际亮度和所需亮度，统计满足条件的位置数量。
时间复杂度: O(m + n)
空间复杂度: O(n)
class Solution:
def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:
pre = [0] * (n + 1) # 创建差分数组
for x, pos in lights:
l, r = max(0, x-pos), min(n-1, x+pos) + 1 # 计算每个灯光的照明范围，并进行差分数组的更新
pre[l] += 1
pre[r] -= 1
count = list(accumulate(pre)) # 通过累加差分数组得到实际亮度数组
# print(count)
result = 0
for x, y in zip(count, requirement):
if x >= y: # 比较实际亮度和所需亮度，统计满足条件的位置数量
result += 1
return result
Explore
在差分数组中，我们使用加1和减1的操作来设定一个区间的增量。当在位置l上加1时，表示从这个位置开始直到数组结束，所有的值都应增加1。为了让这个增加只影响到位置r，我们在位置r+1减1。这样，从位置r+1开始的值就会抵消之前的增加，从而实现了在区间[l, r]内的增加。这种方法使得我们可以用两个操作来高效地表示一个连续区间的增量，而不需要对区间内的每一个元素逐一增加，极大地提高了效率。
在差分数组的实现中，我们通过设置适当的条件检查来确保不会出现索引越界。例如，在本题解中，更新差分数组时使用了`min(n-1, x+pos) + 1`来确定右边界，这保证了即使灯光的照明范围超出了街道的实际长度，数组索引也不会超过定义的边界。这样，通过逻辑上的边界控制，可以安全地更新差分数组而不引发运行时错误。
在这种情况下，差分数组的相关位置（没有灯光覆盖的位置）的增量将保持为零。因为差分数组最初被初始化为全零，只有被灯光覆盖的区域会通过加1和减1操作产生非零值。在后续通过累加差分数组得到实际亮度数组时，没有灯光覆盖的位置的亮度值将保持为零，因此这些区域的亮度直接由差分数组的初始状态和累加过程决定。
确实，除了差分数组，线段树也是处理范围更新问题的一个有效数据结构。线段树的优点包括能够处理更复杂的范围查询和更新操作，比如范围内的最小值、最大值或求和，以及更灵活地处理更新操作的类型。然而，线段树的实现比差分数组复杂，需要更多的内存和更复杂的逻辑来维护树结构。而差分数组则提供了一种空间效率和实现简单的方法来进行区间加法操作，尤其适用于本题这种只需处理区间加法的场景。因此，选择哪种数据结构取决于问题的具体需求和预期的操作类型。