当前位置：首页 > article >正文

Leetcode2012：数组美丽值求和

article 2025/3/12 13:42:06

题目描述：

给你一个下标从 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] 的 美丽值的总和 。

代码思路：

前缀最大值和后缀最小值：
- pre1 是一个数组，保存了从左到右遍历时 nums 的前缀最大值。即，对于每个位置 i，pre1[i] 表示从 nums[0] 到 nums[i] 的最大值。
- pre2 是一个数组，保存了从右到左遍历时 nums 的后缀最小值。即，对于每个位置 i，pre2[i] 表示从 nums[i] 到 nums[n-1] 的最小值（注意 pre2 是通过反转 nums 计算然后再反转回来的）。
初始化：
- 使用 accumulate 函数来计算 pre1 和 pre2。
- ans 初始化为 0，用于累加所有符合条件的 nums[i] 的美丽值。
遍历数组：
- 遍历数组 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。
返回结果：
- 遍历完成后，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

查看全文

http://www.kler.cn/a/581410.html