难度: Medium
Submission
运行时间: 30 ms
内存: 21.5 MB
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
diff = [0] * (length + 1)
res = [0] * length
for l, r, v in updates:
diff[l] += v
diff[r + 1] -= v
for i in range(1, len(diff)):
diff[i] = diff[i] + diff[i - 1]
return diff[:-1]
Explain
这个题解使用了差分数组的思路。首先创建一个长度为 length+1 的差分数组 diff，然后遍历 updates 数组，对于每个区间 [l, r]，在 diff[l] 处加上 v，在 diff[r+1] 处减去 v。这样，diff 数组就记录了每个位置的变化量。最后，对 diff 数组进行前缀和计算，得到原始数组经过所有更新操作后的最终结果。
时间复杂度: O(length + m)
空间复杂度: O(length)
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
# 创建差分数组 diff 和结果数组 res
diff = [0] * (length + 1)
res = [0] * length
# 遍历 updates 数组，更新差分数组 diff
for l, r, v in updates:
diff[l] += v
diff[r + 1] -= v
# 计算差分数组 diff 的前缀和，得到最终结果
for i in range(1, len(diff)):
diff[i] = diff[i] + diff[i - 1]
# 返回 diff 数组的前 length 个元素作为最终结果
return diff[:-1]
Explore
在差分数组的应用中，使用`length + 1`的长度是为了方便处理区间的结束位置。当我们对区间[l, r]加上一个值时，为了只在这个区间内影响，需要在`diff[r+1]`处减去相同的值，这样差分数组在`r+1`的位置就能抵消之前的增加，从而保证增加的值只在区间[l, r]内有效。如果我们只用`length`大小的数组，当`r`等于`length-1`时，我们无法在`diff[r+1]`处减去值，因此会导致数组越界。
为了防止数组越界，在更新差分数组前需要检查`r + 1`是否超出数组的边界。如果`r + 1`等于或超过`length + 1`，我们不应该在`diff[r + 1]`处减去值，因为这会导致越界。实际操作中，可以通过条件语句来确保只在`r + 1`小于`length + 1`时才执行减法操作。这样可以确保更新只对有效的数组索引进行，避免越界错误。
是的，`对 diff 数组进行前缀和计算`的步骤能正确反映多次区间更新的累积效果。差分数组的设计意图就是通过在区间起始位置增加值，在结束位置的下一个位置减少相同的值，来表示区间更新。通过计算差分数组的前缀和，每个位置的值将会是所有之前操作的累积结果，因此能够反映出经过多次更新后每个位置的最终值。
在计算最终结果数组`res`时，可以直接使用`diff`数组的前`length`个元素，因为`diff`数组的最后一个元素（即`diff[length]`）主要用于在`r = length - 1`时结束区间的更新，不需要包含在最终结果数组中。通过计算前缀和，`diff`数组已经将所有更新操作正确地反映在了每个元素上。由于原始数组长度为`length`，我们只需要`diff`数组的前`length`个元素来得到最终结果。