数组美丽值求和
难度:
标签:
题目描述
代码结果
运行时间: 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`?
▷🦆
在遍历数组计算美丽值时,如何确保`pre_max`和`suf_min[i+1]`的值能够准确地反映出在第`i`位置前后的最大和最小值?
▷🦆
解法中提到的条件`pre_max < v < suf_min[i+1]`和`nums[i-1] < v < nums[i+1]`是否有可能同时满足?如果是,算法如何处理这种情况?
▷