区间加法
难度:
标签:
题目描述
代码结果
运行时间: 30 ms, 内存: 21.5 MB
/*
* 解题思路:
* 1. 初始化一个长度为n的零数组。
* 2. 使用流处理每一个操作,对于每一个操作,从start到end的所有元素都加上inc。
* 3. 返回最终的数组。
*/
import java.util.Arrays;
public class IntervalAdditionStream {
public static int[] applyOperations(int n, int[][] operations) {
int[] result = new int[n];
Arrays.stream(operations).forEach(operation -> {
int start = operation[0];
int end = operation[1];
int inc = operation[2];
for (int i = start; i <= end; i++) {
result[i] += inc;
}
});
return result;
}
public static void main(String[] args) {
int n = 5;
int[][] operations = {{1, 3, 2}, {2, 4, 3}, {0, 2, -2}};
int[] result = applyOperations(n, operations);
Arrays.stream(result).forEach(num -> System.out.print(num + " "));
}
}
解释
方法:
这个题解使用了差分数组的思路。首先创建一个长度为 length+1 的差分数组 diff,然后遍历 updates 数组,对于每个区间 [l, r],在 diff[l] 处加上 v,在 diff[r+1] 处减去 v。这样,diff 数组就记录了每个位置的变化量。最后,对 diff 数组进行前缀和计算,得到原始数组经过所有更新操作后的最终结果。
时间复杂度:
O(length + m)
空间复杂度:
O(length)
代码细节讲解
🦆
在题解中,为什么要使用长度为`length + 1`的差分数组而不是`length`?
▷🦆
如果更新操作的区间`[l, r]`中的`r >= length`,该如何处理以避免数组越界错误?
▷🦆
题解中提到的`对 diff 数组进行前缀和计算`步骤是否能正确反映多次区间更新的累积效果?
▷🦆
在计算最终结果数组`res`时,为什么可以直接使用`diff`数组的前`length`个元素,不需要另外处理最后一个元素?
▷相关问题
区间加法 II
给你一个 m x n
的矩阵 M
和一个操作数组 op
。矩阵初始化时所有的单元格都为 0
。ops[i] = [ai, bi]
意味着当所有的 0 <= x < ai
和 0 <= y < bi
时, M[x][y]
应该加 1。
在 执行完所有操作后 ,计算并返回 矩阵中最大整数的个数 。
示例 1:
输入: m = 3, n = 3,ops = [[2,2],[3,3]] 输出: 4 解释: M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。
示例 2:
输入: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]] 输出: 4
示例 3:
输入: m = 3, n = 3, ops = [] 输出: 9
提示:
1 <= m, n <= 4 * 104
0 <= ops.length <= 104
ops[i].length == 2
1 <= ai <= m
1 <= bi <= n