一、什么是差分数组
差分数组是一种高效处理区间更新操作的数据结构技巧,特别适用于需要对数组的某个区间进行频繁增减操作的场景。差分数组的核心思想是通过存储相邻元素的差值而非元素本身,将区间操作转化为端点操作,从而将时间复杂度从O(n)降低到O(1)。
给定一个原始数组arr
,其对应的差分数组diff
定义为:
diff[i] = arr[i] - arr[i-1] (i > 0)
diff[0] = arr[0] (i = 0)
例如:
原始数组: [1, 3, 6, 8, 5]
差分数组: [1, 2, 3, 2, -3]
二、差分数组的优势
差分数组的主要优势在于它可以高效处理区间更新操作。对于传统的数组,如果我们想对区间[i, j]内的所有元素增加一个值val,需要遍历整个区间进行逐个修改,时间复杂度为O(n)。而使用差分数组,我们只需要修改两个端点:
diff[i] += val
diff[j+1] -= val
(如果j+1在数组范围内)
这样就将区间操作的时间复杂度从O(n)降低到了O(1)。
三、差分数组的实现
1. 构建差分数组
vector<int> buildDiffArray(const vector<int>& arr) {
int n = arr.size();
vector<int> diff(n);
diff[0] = arr[0];
for (int i = 1; i < n; ++i) {
diff[i] = arr[i] - arr[i-1];
}
return diff;
}
2. 区间更新操作
void updateRange(vector<int>& diff, int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.size()) {
diff[j+1] -= val;
}
}
3. 还原原始数据
vector<int> restoreArray(const vector<int>& diff) {
int n = diff.size();
vector<int> arr(n);
arr[0] = diff[0];
for (int i = 1; i < n; ++i) {
arr[i] = arr[i-1] + diff[i];
}
return arr;
}
四、差分数组的应用场景
差分数组特别适用于以下场景:
- 频繁的区间增减操作
- 需要多次区间操作后查询最终结果
- 处理大量区间覆盖问题
- 航班预订、会议室安排等问题
五、LeetCode例题解析
1. 航班预订统计(1109. Corporate Flight Bookings)
题目链接:leetcode.com/problems/co…
题目描述:有n个航班,编号从1到n。给定一个航班预订表bookings,其中bookings[i] = [firsti, lasti, seatsi]表示在firsti到lasti的每个航班上预订了seatsi个座位。返回一个长度为n的数组answer,表示每个航班上预订的座位总数。
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int> diff(n + 1, 0); // 使用n+1大小避免边界检查
for (const auto& booking : bookings) {
int first = booking[0] - 1; // 转换为0-based
int last = booking[1] - 1;
int seats = booking[2];
diff[first] += seats;
if (last + 1 < n) {
diff[last + 1] -= seats;
}
}
vector<int> answer(n);
answer[0] = diff[0];
for (int i = 1; i < n; ++i) {
answer[i] = answer[i-1] + diff[i];
}
return answer;
}
2. 拼车(1094. Car Pooling)
题目链接:leetcode.com/problems/ca…
题目描述:一辆车有capacity个座位,给定trips数组,其中trips[i] = [numPassengers, from, to]表示有numPassengers乘客在from上车,在to下车。判断车辆是否能完成所有行程(任何时候乘客数不超过capacity)。
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> diff(1001, 0); // 题目中0 <= from < to <= 1000
for (const auto& trip : trips) {
int passengers = trip[0];
int from = trip[1];
int to = trip[2];
diff[from] += passengers;
diff[to] -= passengers;
}
int current = 0;
for (int i = 0; i <= 1000; ++i) {
current += diff[i];
if (current > capacity) {
return false;
}
}
return true;
}
3. 区间加法(370. Range Addition)
题目链接:leetcode.com/problems/ra…
题目描述:给定一个初始长度为length的全0数组,和一系列更新操作updates,其中updates[i] = [startIdx, endIdx, inc],表示将子数组[startIdx, endIdx]中的每个元素增加inc。返回执行完所有操作后的数组。
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
vector<int> diff(length, 0);
for (const auto& update : updates) {
int start = update[0];
int end = update[1];
int inc = update[2];
diff[start] += inc;
if (end + 1 < length) {
diff[end + 1] -= inc;
}
}
vector<int> result(length);
result[0] = diff[0];
for (int i = 1; i < length; ++i) {
result[i] = result[i-1] + diff[i];
}
return result;
}
六、差分数组的变种与扩展
1. 二维差分数组
差分数组的概念可以扩展到二维,用于处理二维矩阵的区间更新问题。二维差分数组的更新需要修改四个角:
// 更新矩形区域(x1,y1)到(x2,y2)
void update2D(vector<vector<int>>& diff, int x1, int y1, int x2, int y2, int val) {
diff[x1][y1] += val;
if (x2 + 1 < diff.size()) {
diff[x2+1][y1] -= val;
}
if (y2 + 1 < diff[0].size()) {
diff[x1][y2+1] -= val;
}
if (x2 + 1 < diff.size() && y2 + 1 < diff[0].size()) {
diff[x2+1][y2+1] += val;
}
}
2. 差分数组与线段树的比较
差分数组和线段树都可以处理区间更新问题,但各有优劣:
特性 | 差分数组 | 线段树 |
---|---|---|
区间更新复杂度 | O(1) | O(logn) |
单点查询复杂度 | O(n) | O(logn) |
空间复杂度 | O(n) | O(n) |
实现难度 | 简单 | 较复杂 |
选择依据:
- 如果只有区间更新,最后才查询结果,选择差分数组
- 如果需要边更新边查询,选择线段树
七、总结
差分数组是一种简单而强大的技巧,特别适合处理大量区间更新操作后查询结果的场景。它通过将区间操作转化为端点操作,大幅提高了算法效率。掌握差分数组不仅可以帮助我们解决许多LeetCode问题,在实际工程中也有广泛应用,如资源调度、时间线处理等场景。
通过本文的三个LeetCode例题,我们可以看到差分数组如何优雅地解决看似复杂的问题。建议读者在理解基本原理后,多练习相关题目,以加深对这一技巧的掌握。