©2020-2024 ioDraw All rights reserved,
Privacy Policy
一、基本概念
差分算法是前缀和算法的逆运算，可以快速的对数组的某一区间进行计算操作。
例如，有一数列 a[1],a[2],.…a[n]，且令 b[i] = a[i]-a[i-1],b[1]=a[1]，那么就有
a[i] = b[1]+b[2]+.…+b[i] =
a[1]+a[2]-a[1]+a[3]-a[2]+.…+a[i]-a[i-1]，此时b数组称作a数组的差分数组
，换句话来说a数组就是b数组的前缀和数组 例：
原始数组a：9 3 6 2 6 8
差分数组b：9 -6 3 -4 4 2
可以看到a数组是b数组的前缀和数组。
那么现在有一个任务：对数组a区间[left,right]每个元素加一个常数c。这时可以利用原数组就是差分数组的前缀和这个特性，来解决这个问题。对于b数组，只需要执行
b[left] += c, b[right+1] −= c
二、leetcode例题
leetcode-1094-拼车
bool carPooling(vector<vector<int>>& trips, int capacity) { vector<int>
origin(1001,0); vector<int> difference(1001,0); int num; int left; int right;
int PrefixSum = 0; // 计算差分数组 for (int i = 0; i < trips.size(); ++i) { num =
trips[i][0]; left = trips[i][1]; right = trips[i][2]; difference[left] += num;
difference[right -1 + 1] -= num; } // 求差分数组的前缀和数组，即原数组 for (int i = 0; i <
difference.size(); ++i) { PrefixSum += difference[i]; origin[i] = PrefixSum; }
// 判断是否有超员 for (int i = 0; i < origin.size(); ++i) { if (origin[i] > capacity)
{ return false; } } return true; }
leetcode-1109-航班预定统计