【Leetcode 每日一题】2012. 数组美丽值求和

问题背景

给你一个下标从 $0$ 开始的整数数组 $nums$。对于每个下标 $i(1\le i\le nums.length-2)$，$nums[i]$ 的 美丽值 等于：

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

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

数据约束

• $3\le nums.length\le 10^5$
• $1\le nums[i]\le 10^5$

解题过程

主要的难点是理解这些数学表达式，实际上只要求出前缀最大值和后缀最小值，在遍历的过程中根据不同情况累计相应的值即可。
可以将求前后缀数组的过程优化到计算答案的循环中，但是时间性能没有数量级上的提升，就不单独写了。

具体实现

class Solution {
    public int sumOfBeauties(int[] nums) {
        int n = nums.length;
        int[] preMax = new int[n];
        int[] sufMax = new int[n];
        preMax[0] = nums[0];
        sufMax[n - 1] = nums[n - 1];
        for (int i = 1; i < n; i++) {
            preMax[i] = Math.max(preMax[i - 1], nums[i]);
        }
        for (int i = n - 2; i >= 0; i--) {
            sufMax[i] = Math.min(sufMax[i + 1], nums[i]);
        }
        int res = 0;
        for (int i = 1; i < n - 1; i++) {
            res += preMax[i - 1] < nums[i] && nums[i] < sufMax[i + 1] ? 2 : (nums[i - 1] < nums[i] && nums[i] < nums[i + 1] ? 1 : 0);
        }
        return res;
    }
}