leetcode
leetcode 1751 ~ 1800
数组美丽值求和

数组美丽值求和

难度:

标签:

题目描述

代码结果

运行时间: 116 ms, 内存: 28.2 MB


/*
 * 思路:
 * 1. 使用 Java Stream API 进行简化处理。
 * 2. 我们无法直接使用 Stream API 中的组合方法,但可以使用 IntStream 和辅助方法进行类似的遍历。
 * 3. 通过 IntStream.range() 遍历并计算美丽值。
 */
import java.util.stream.IntStream;

public int sumOfBeauties(int[] nums) {
    int n = nums.length;
    return IntStream.range(1, n - 1).map(i -> {
        if (IntStream.range(0, i).anyMatch(j -> nums[j] < nums[i]) &&
            IntStream.range(i + 1, n).anyMatch(k -> nums[i] < nums[k])) {
            return 2;
        } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
            return 1;
        } else {
            return 0;
        }
    }).sum();
}

解释

方法:

这个解法首先通过构建一个后缀最小数组`suf_min`来快速获取任意位置i之后元素的最小值。这个数组从后向前填充,保证每个位置存储从当前位置到数组末尾的最小值。然后,使用一个变量`pre_max`来跟踪从数组开始到当前位置的最大值。对于数组中的每个元素,我们检查两个条件来决定其美丽值:1) 如果该元素大于之前所有元素的最大值且小于之后所有元素的最小值,则其美丽值为2。2) 如果不满足第一个条件,但该元素大于其前一个元素且小于其后一个元素,则其美丽值为1。使用这两个辅助结构(后缀最小数组和前缀最大值),我们能在一次遍历中计算出所有元素的美丽值。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在构建后缀最小数组`suf_min`时,循环的起始索引是从`n-2`开始而不是`n-1`?
在构建后缀最小数组`suf_min`时,数组的最后一个元素自身就是它之后所有元素的最小值,因为它之后没有其他元素。因此,`suf_min[n-1]`直接设为`nums[n-1]`。接着,为了填充数组的其余部分,我们需要从倒数第二个元素开始向前遍历,即从`n-2`开始。这样可以确保每个位置`i`的`suf_min[i]`正确地存储从位置`i`到数组末尾的最小值。如果从`n-1`开始,那么我们将没有需要处理的元素,因为最后一个元素已被初始化。
🦆
在遍历数组计算美丽值时,如何确保`pre_max`和`suf_min[i+1]`的值能够准确地反映出在第`i`位置前后的最大和最小值?
在遍历数组计算每个元素的美丽值时,使用`pre_max`来跟踪从数组开始到当前位置前一个元素的最大值,这是通过在遍历中不断更新`pre_max`实现的,确保每到新的位置`i`,`pre_max`代表的是`0`到`i-1`的最大值。同时,`suf_min`数组已经在之前被构建完成,其中`suf_min[i+1]`存储了从位置`i+1`到数组末尾的最小值。这样,在计算位置`i`的美丽值时,可以直接使用`pre_max`和`suf_min[i+1]`来准确反映出位置`i`前后的值。
🦆
解法中提到的条件`pre_max < v < suf_min[i+1]`和`nums[i-1] < v < nums[i+1]`是否有可能同时满足?如果是,算法如何处理这种情况?
这两个条件是用来确定数组中每个元素的美丽值的,但它们关注的范围和条件不同。条件`pre_max < v < suf_min[i+1]`关注的是元素`v`是否是其前面所有元素的最大值,并且是其后面所有元素的最小值。而条件`nums[i-1] < v < nums[i+1]`只关注元素`v`与其直接相邻的两个元素。理论上,这两个条件有可能同时满足,但在我们的算法中,如果`pre_max < v < suf_min[i+1]`条件满足,则美丽值为2,此时不需要再考虑`nums[i-1] < v < nums[i+1]`的情况。因此,即使两个条件同时满足,元素的美丽值也会被算作2,这是因为2代表了更高的美丽值级别。

相关问题