数组美丽值求和

标签: 数组

难度: Medium

给你一个下标从 0 开始的整数数组 nums 。对于每个下标 i（1 <= i <= nums.length - 2），nums[i] 的 美丽值 等于：

  • 2，对于所有 0 <= j < i 且 i < k <= nums.length - 1 ，满足 nums[j] < nums[i] < nums[k]
  • 1，如果满足 nums[i - 1] < nums[i] < nums[i + 1] ，且不满足前面的条件
  • 0，如果上述条件全部不满足

返回符合 1 <= i <= nums.length - 2 的所有 nums[i] 的 美丽值的总和 。

示例 1：

输入：nums = [1,2,3]
输出：2
解释：对于每个符合范围 1 <= i <= 1 的下标 i :
- nums[1] 的美丽值等于 2

示例 2：

输入：nums = [2,4,6,4]
输出：1
解释：对于每个符合范围 1 <= i <= 2 的下标 i :
- nums[1] 的美丽值等于 1
- nums[2] 的美丽值等于 0

示例 3：

输入：nums = [3,2,1]
输出：0
解释：对于每个符合范围 1 <= i <= 1 的下标 i :
- nums[1] 的美丽值等于 0

提示：

  • 3 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Submission

运行时间: 116 ms

内存: 28.2 MB

class Solution:
    def sumOfBeauties(self, nums: List[int]) -> int:
        n = len(nums)
        suf_min = [0] * n # 后缀最小值
        suf_min[n-1] = nums[n-1]
        for i in range(n-2, 1, -1):
            suf_min[i] = min(suf_min[i+1], nums[i])
        pre_max = nums[0]
        ans = 0
        for i in range(1, n-1):
            v = nums[i]
            if pre_max < v < suf_min[i+1]:
                ans += 2
            elif nums[i-1] < v < nums[i+1]:
                ans += 1
            
            if v > pre_max:
                pre_max = v
        return ans

Explain

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

时间复杂度: O(n)

空间复杂度: O(n)

# 定义Solution类
class Solution:
    def sumOfBeauties(self, nums: List[int]) -> int:
        n = len(nums) # 获取数组长度
        suf_min = [0] * n # 初始化后缀最小数组
        suf_min[n-1] = nums[n-1] # 最后一个元素的后缀最小就是它本身
        for i in range(n-2, 1, -1): # 填充后缀最小数组
            suf_min[i] = min(suf_min[i+1], nums[i]) # 取当前元素和后一个后缀最小的较小者
        pre_max = nums[0] # 初始化前缀最大值
        ans = 0 # 美丽值总和初始化为0
        for i in range(1, n-1): # 遍历数组中的每个元素
            v = nums[i] # 当前元素值
            if pre_max < v < suf_min[i+1]: # 检查是否满足美丽值为2的条件
                ans += 2
            elif nums[i-1] < v < nums[i+1]: # 检查是否满足美丽值为1的条件
                ans += 1
            if v > pre_max: # 更新前缀最大值
                pre_max = v
        return ans # 返回总美丽值

Explore

在构建后缀最小数组`suf_min`时，数组的最后一个元素自身就是它之后所有元素的最小值，因为它之后没有其他元素。因此，`suf_min[n-1]`直接设为`nums[n-1]`。接着，为了填充数组的其余部分，我们需要从倒数第二个元素开始向前遍历，即从`n-2`开始。这样可以确保每个位置`i`的`suf_min[i]`正确地存储从位置`i`到数组末尾的最小值。如果从`n-1`开始，那么我们将没有需要处理的元素，因为最后一个元素已被初始化。

在遍历数组计算每个元素的美丽值时，使用`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]`关注的是元素`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代表了更高的美丽值级别。