统计隐藏数组数目
难度:
标签:
题目描述
代码结果
运行时间: 88 ms, 内存: 30.0 MB
/*
* 思路:
* 1. 使用Java Stream API来计算最大最小值和累计和。
* 2. 通过映射每个differences元素来计算累计和,使用Collectors来获取最大最小值。
* 3. 最后计算有效的hidden数组数量。
*/
import java.util.*;
import java.util.stream.*;
public int numberOfArraysStream(int[] differences, int lower, int upper) {
long[] sums = new long[differences.length + 1];
Arrays.setAll(sums, i -> i == 0 ? 0 : sums[i - 1] + differences[i - 1]);
long minHidden = Arrays.stream(sums).min().orElse(0);
long maxHidden = Arrays.stream(sums).max().orElse(0);
long maxAllowed = upper - lower;
if (maxHidden - minHidden > maxAllowed) return 0;
return (int) (maxAllowed - (maxHidden - minHidden) + 1);
}
解释
方法:
本题解首先通过累加 differences 数组得到一个新数组 arr,该数组代表从某个起始值开始的隐藏数组各个位置的相对变化。通过计算 arr 数组与初始值 0 的最大值和最小值,可以确定隐藏数组值的可能范围。接着,我们计算这个范围与给定的 lower 和 upper 之间是否有重叠,并计算这个重叠区间的大小。如果重叠区间的长度为正,则这就是符合条件的隐藏数组的数量;否则,返回 0。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在解题中需要将 differences 数组的累加和计算为一个新数组,这个新数组 arr 有什么特别的意义或作用?
▷🦆
在计算 arr 数组的最小值和最大值时,为什么要包括 0 作为比较的一个元素?
▷🦆
在计算隐藏数组可能的起始值范围时,表达式 `upper - mx - (lower - mn) + 1` 是如何推导出来的?请解释其逻辑。
▷🦆
如果 differences 数组全为正或全为负,这会对解题逻辑的有效性产生什么影响?
▷