前缀和
-
差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。
- 如果你想对区间
nums[i..j]的元素全部加 3，那么只需要让diff[i] += 3，然后再让diff[j+1] -= 3即可：
370. Range Addition
- 思路
- example
- 前缀和数组与差分数组的相互转换
diff[0] = nums[0]
diff[i] = nums[i] - nums[i-1]
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
# diff[i] = nums[i] - nums[i-1], diff[0] = nums[0]
diff = [0 for _ in range(length)]
for update in updates:
start, end, increment = update[0], update[1], update[2]
diff[start] += increment
if end + 1 < length:
diff[end+1] -= increment
# nums[i] = nums[i-1] + diff[i]
nums = [0 for _ in range(length)]
nums[0] = diff[0]
for i in range(1, length):
nums[i] = nums[i-1] + diff[i]
return nums
1109. Corporate Flight Bookings
- 思路
- example
- 转化为差分问题
- 复杂度. 时间：O(?), 空间: O(?)
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
diff = [0 for _ in range(n)]
for i, j, inc in bookings:
i -= 1
j -= 1 # shift index
diff[i] += inc
if j < n-1:
diff[j+1] -= inc
nums = [0 for _ in range(n)]
nums[0] = diff[0]
for i in range(1, n):
nums[i] = nums[i-1] + diff[i]
return nums
1094. Car Pooling
- 思路
- example
- 1 <= trips.length <= 1000, 0 <= fromi < toi <= 1000
- 复杂度. 时间：O(?), 空间: O(?)
from_i,..., to_i-1
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
diff = [0 for _ in range(1001)]
for inc, start, end in trips:
end -= 1 # !!! 在这里下车
diff[start] += inc
if end < 1000:
diff[end+1] -= inc
nums = [0 for _ in range(1001)]
nums[0] = diff[0]
if nums[0] > capacity:
return False
for i in range(1, 1001):
nums[i] = nums[i-1] + diff[i]
if nums[i] > capacity:
return False
return True
