c++ - 求一系列数字加减后的最小值和最大值

Question

我有一道算法题，其中给出了从 1 到 N 的数字，并且要执行一些操作，然后必须在其中找到最小值/最大值。

两个运算——加法和减法

运算的形式为 a b c d ，其中a是要执行的运算，b是起始数，c是结束数，d是要加/减的数

例如

suppose numbers are 1 to N and N =5

1 2 3 4 5

我们按照以下方式执行操作

1 2 4 5

2 1 3 4

1 4 5 6

通过这些操作，我们将得到从 1 到 N 的数字

1 7 8 9 5

-3 3 4 9 5

-3 3 4 15 11

所以最大值是15，最小值是-3

我的方法:我已经取了数字的下限和上限，在这种情况下它是 1 和 5 仅存储在一个数组中并应用操作，然后找到最小值和最大值。

有没有更好的方法？

Answer 1

我假设所有更新(加法/减法)操作都发生在找到最大值/最小值之前。对于将更新和最小/最大操作混合在一起，我没有好的解决方案。

您可以使用普通数组，其中数组索引 i 处的值是索引 i 与原始数组索引 (i - 1) 之间的差值。这使得从我们数组的索引 0 到索引 i 的总和成为原始数组的索引 i 处的值。

减法是与取反的数相加，所以它们可以类似地处理。当我们需要将 k 添加到从索引 i 到索引 j 的原始数组时，我们将 k 添加到我们数组的索引 i，并减去 k 到我们数组的索引 (j + 1)。每次更新需要 O(1) 时间。

您可以通过累加求和并记录最大/最小值来找到原始数组的最小/最大。每次操作需要 O(n) 时间。我假设这是对整个阵列完成一次。

伪代码:

a[N] // Original array
d[N] // Difference array

// Initialization
d[0] = a[0]
for (i = 1 to N-1)
    d[i] = a[i] - a[i - 1]

// Addition (subtraction is similar)
add(from_idx, to_idx, amount) {
    d[from_idx] += amount
    d[to_idx + 1] -= amount
}

// Find max/min for the WHOLE array after add/subtract
current = max = min = d[0];
for (i = 1 to N - 1) {
   current += d[i]; // Sum from d[0] to d[i] is a[i]
   max = MAX(max, current);
   min = MIN(min, current);
}