leetcode
leetcode 301 ~ 350
区间加法

区间加法

难度:

标签:

题目描述

代码结果

运行时间: 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`?
在差分数组的应用中,使用`length + 1`的长度是为了方便处理区间的结束位置。当我们对区间[l, r]加上一个值时,为了只在这个区间内影响,需要在`diff[r+1]`处减去相同的值,这样差分数组在`r+1`的位置就能抵消之前的增加,从而保证增加的值只在区间[l, r]内有效。如果我们只用`length`大小的数组,当`r`等于`length-1`时,我们无法在`diff[r+1]`处减去值,因此会导致数组越界。
🦆
如果更新操作的区间`[l, r]`中的`r >= length`,该如何处理以避免数组越界错误?
为了防止数组越界,在更新差分数组前需要检查`r + 1`是否超出数组的边界。如果`r + 1`等于或超过`length + 1`,我们不应该在`diff[r + 1]`处减去值,因为这会导致越界。实际操作中,可以通过条件语句来确保只在`r + 1`小于`length + 1`时才执行减法操作。这样可以确保更新只对有效的数组索引进行,避免越界错误。
🦆
题解中提到的`对 diff 数组进行前缀和计算`步骤是否能正确反映多次区间更新的累积效果?
是的,`对 diff 数组进行前缀和计算`的步骤能正确反映多次区间更新的累积效果。差分数组的设计意图就是通过在区间起始位置增加值,在结束位置的下一个位置减少相同的值,来表示区间更新。通过计算差分数组的前缀和,每个位置的值将会是所有之前操作的累积结果,因此能够反映出经过多次更新后每个位置的最终值。
🦆
在计算最终结果数组`res`时,为什么可以直接使用`diff`数组的前`length`个元素,不需要另外处理最后一个元素?
在计算最终结果数组`res`时,可以直接使用`diff`数组的前`length`个元素,因为`diff`数组的最后一个元素(即`diff[length]`)主要用于在`r = length - 1`时结束区间的更新,不需要包含在最终结果数组中。通过计算前缀和,`diff`数组已经将所有更新操作正确地反映在了每个元素上。由于原始数组长度为`length`,我们只需要`diff`数组的前`length`个元素来得到最终结果。

相关问题

区间加法 II

给你一个 m x n 的矩阵 M 和一个操作数组 op 。矩阵初始化时所有的单元格都为 0ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai0 <= 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