Leetcode2012：数组美丽值求和

题目描述：

给你一个下标从 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. 前缀最大值和后缀最小值 ：
   • pre1 是一个数组，保存了从左到右遍历时 nums 的前缀最大值。即，对于每个位置 i ， pre1[i] 表示从 nums[0] 到 nums[i] 的最大值。
   • pre2 是一个数组，保存了从右到左遍历时 nums 的后缀最小值。即，对于每个位置 i ， pre2[i] 表示从 nums[i] 到 nums[n-1] 的最小值（注意 pre2 是通过反转 nums 计算然后再反转回来的）。
2. 初始化 ：
   • 使用 accumulate 函数来计算 pre1 和 pre2 。
   • ans 初始化为 0，用于累加所有符合条件的 nums[i] 的美丽值。
3. 遍历数组 ：
   • 遍历数组 nums 的每个元素（从下标 1 到 len(nums) - 2 ），计算每个 nums[i] 的美丽值。
   • 对于每个 i ：
     • 如果 nums[i] 满足条件 pre1[i - 1] < nums[i] < pre2[i + 1] ，即比左侧所有元素都大且比右侧所有元素都小，则美丽值为 2，累加到 ans 。
     • 否则如果 nums[i] 满足条件 nums[i - 1] < nums[i] < nums[i + 1] ，即仅比相邻的两个元素大，则美丽值为 1，累加到 ans 。
4. 返回结果 ：
   • 遍历完成后， ans 就是符合条件的所有 nums[i] 的美丽值总和，返回 ans 。

代码实现：

class Solution:
    def sumOfBeauties(self, nums: List[int]) -> int:
        pre1, pre2, ans = list(accumulate(nums, func = max)), list(accumulate(nums[::-1], func = min))[::-1], 0
        for i in range(1, len(nums) - 1):
            if   pre1[i - 1] < nums[i] < pre2[i + 1]: ans += 2
            elif nums[i - 1] < nums[i] < nums[i + 1]: ans += 1
        return ans