数组美丽值求和 (Leetcode 2012)

数组美丽值求和 (Leetcode 2012)

题目描述

给你一个下标从 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

示例 2：

输入：nums = [2,4,6,4]
输出：1

示例 3：

输入：nums = [3,2,1]
输出：0

提示：

• 3 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

思路解析

如果直接采用暴力解法，复杂度为 O(n^2)，会超时。

我们可以用 前缀最大值 和 后缀最小值 来优化 O(n^2) 的查询，降低时间复杂度。

• max_[i] 记录 nums[0:i] 的最大值
• min_[i] 记录 nums[i+1:n] 的最小值

这样可以减少 max(nums[0:i]) 和 min(nums[i+1:n]) 的重复计算，提高效率。

代码实现

from typing import List

class Solution:
    def sumOfBeauties(self, nums: List[int]) -> int:
        n, res = len(nums), 0
        max_ = [-2e9] * n  # 前缀最大值
        min_ = [2e9] * n    # 后缀最小值
        
        # 计算前缀最大值
        for i in range(1, n):
            max_[i] = max(max_[i-1], nums[i-1])
        
        # 计算后缀最小值
        for i in range(n-2, 0, -1):
            min_[i] = min(min_[i+1], nums[i+1])
        
        # 遍历数组，计算美丽值
        for i in range(1, n-1):
            if max_[i] < nums[i] and min_[i] > nums[i]:
                res += 2
            elif nums[i-1] < nums[i] < nums[i+1]:
                res += 1
        
        return res

复杂度分析

• 时间复杂度：O(n)

  • 计算 max_ 数组：O(n)
  • 计算 min_ 数组：O(n)
  • 遍历数组计算美丽值：O(n)
  • 总体复杂度为 O(n)

• 空间复杂度：O(n)

  • 额外的 max_ 和 min_ 数组占用 O(n) 额外空间。

总结

• 暴力解法时间复杂度 O(n^2)，不可行。
• 通过 前缀最大值 和 后缀最小值 优化，时间复杂度降至 O(n)。
• 该方法适用于 需要动态查询区间最大/最小值 的问题。

扩展思考

如果 nums 规模进一步增大，我们可以考虑 滑动窗口 或 单调栈 方法来进一步优化空间复杂度。