leetcode
leetcode 1851 ~ 1900
统计隐藏数组数目

统计隐藏数组数目

难度:

标签:

题目描述

代码结果

运行时间: 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 有什么特别的意义或作用?
在本题中,differences 数组中的每个元素表示隐藏数组相邻元素之间的差值。通过将 differences 数组的元素累加,我们可以重构出隐藏数组相对于起始元素的每个位置的值。这个新数组 arr 不直接代表隐藏数组的绝对值,而是表示从起始元素开始的相对变化。这种重构是理解和计算隐藏数组在给定范围内可能的起始值的关键步骤。
🦆
在计算 arr 数组的最小值和最大值时,为什么要包括 0 作为比较的一个元素?
在 arr 数组中包含 0 是因为 arr 数组是从某个未知的起始点开始计算的,而这个起始点是我们设为 0 的相对点。包括 0 的目的是确保在计算隐藏数组的可能起始值时能够考虑到整个数组的范围,包括起始点本身。这样我们就可以正确计算出隐藏数组的实际最小值和最大值,并据此推断出符合条件的起始值范围。
🦆
在计算隐藏数组可能的起始值范围时,表达式 `upper - mx - (lower - mn) + 1` 是如何推导出来的?请解释其逻辑。
这个表达式是为了确定隐藏数组所有元素都在给定的 lower 和 upper 范围内的有效起始值的数量。给定 arr 数组中的最小值 mn 和最大值 mx,隐藏数组的起始值需要在一个特定的范围内才能确保整个数组的值都在 [lower, upper] 内。此范围由两部分确定:隐藏数组的最大值不能超过 upper,因此起始值最大为 `upper - mx`;隐藏数组的最小值不能低于 lower,因此起始值最小为 `lower - mn`。两者形成一个闭区间 `[lower - mn, upper - mx]`。`upper - mx - (lower - mn) + 1` 计算的是这个区间内整数的个数。
🦆
如果 differences 数组全为正或全为负,这会对解题逻辑的有效性产生什么影响?
如果 differences 数组全为正或全为负,这意味着 arr 数组将呈现单调递增或单调递减的形态。这将直接影响到计算 mn 和 mx 时的结果,即 arr 数组的极端值将更加极端(更大或更小)。这种极端情况可能会导致计算出的起始值范围非常小或者没有有效的起始值(即范围内没有整数)。然而,解题逻辑仍然有效,因为它正确地处理了这种极端情况,即使结果可能是返回 0 个有效数组。

相关问题