力扣2012题：使用动态规划解决数组美丽值求和

一、题目解读

力扣2012题要求计算数组中所有“美丽数”的总和。美丽数定义为：数组中满足“中间元素同时大于左右相邻元素”或“中间元素同时小于左右相邻元素”的数值。例如，[3,1,2,4]中，1和2均为美丽数，总和为3。

二、解题思路

采用动态规划预处理极值的解法，核心思想：

1. 预处理左右极值：

○ 计算每个位置左侧的最大值（left_max），从前往后遍历，更新当前位置的最大值；

○ 计算每个位置右侧的最小值（right_min），从后往前遍历，更新当前位置的最小值。

2. 遍历中间元素：

○ 若中间元素同时大于left_max和小于right_min，则为严格美丽数，贡献2分；

○ 若中间元素仅满足“山谷”或“山峰”（即两侧相邻元素递增或递减），贡献1分。

3. 累加所有贡献得到总和。

关键在于通过预处理减少重复比较，将O(n^2)复杂度降为O(n)。

三、解题步骤

1. 预处理左侧最大值left_max：

○ 初始化left_max[0] = nums[0]，即第一个元素为左侧最大值；

○ 遍历i=1至n-1，更新left_max[i] = max(left_max[i-1], nums[i])。

2. 预处理右侧最小值right_min：

○ 初始化right_min[n-1] = nums[n-1]，即最后一个元素为右侧最小值；

○ 逆序遍历i=n-2至0，更新right_min[i] = min(right_min[i+1], nums[i])。

3. 计算美丽值总和：

○ 遍历i=1至n-2（中间元素），分情况累加：

■ 若nums[i] > left_max[i-1]且nums[i] < right_min[i+1]，贡献2分；

■ 若nums[i-1] < nums[i]且nums[i] > nums[i+1]（山谷），或反之（山峰），贡献1分。

4. 返回总分数res。

四、代码与注释

class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        int n = nums.size();
        vector<int> left_max(n), right_min(n);
        
        // 预处理左边最大值
        left_max[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            left_max[i] = max(left_max[i-1], nums[i]);
        }
        
        // 预处理右边最小值
        right_min[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; --i) {
            right_min[i] = min(right_min[i+1], nums[i]);
        }
        
        int res = 0;
        // 计算每个中间元素的美丽值
        for (int i = 1; i < n-1; ++i) {
            if (left_max[i-1] < nums[i] && nums[i] < right_min[i+1]) {
                res += 2;
            } else if (nums[i-1] < nums[i] && nums[i] < nums[i+1]) {
                res += 1;
            }
        }
        return res;
    }
};

注释说明：

● left_max[i] = max(...)：动态规划核心，确保每个位置记录左侧最大极值；

● if (left_max[i-1] < nums[i]...：通过预处理结果直接判断美丽数类型，无需重复比较。

五、总结

本文通过动态规划预处理左右极值，高效求解美丽数总和。核心优势在于：

1. 空间换时间：通过O(n)预处理避免O(n^2)比较；

2. 清晰的分情况讨论：严格美丽数与“山谷/山峰”贡献不同分值；

3. 简洁代码实现，无需额外数据结构。

算法时间复杂度O(n)，空间复杂度O(n)，为数组优化问题的典型解法，适用于需要高效处理局部极值的场景，适合算法竞赛与编程学习参考。