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
解释：对于每个符合范围 1 <= i <= 1 的下标 i :

• nums[1] 的美丽值等于 2
  示例 2：

输入：nums = [2,4,6,4]
输出：1
解释：对于每个符合范围 1 <= i <= 2 的下标 i :

• nums[1] 的美丽值等于 1
• nums[2] 的美丽值等于 0
  示例 3：

输入：nums = [3,2,1]
输出：0
解释：对于每个符合范围 1 <= i <= 1 的下标 i :

• nums[1] 的美丽值等于 0

提示：

3 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

尝试做法

class Solution {
    public int sumOfBeauties(int[] nums) {
        int ans = 0;
        int len = nums.length;
        int[] preMax = new int[len];
        int[] postMin = new int[len];
        preMax[0] = nums[0];
        postMin[len - 1] = nums[len - 1];
        for(int i = 1; i < len - 1; ++i){
            if(nums[i] > preMax[i-1]){
                preMax[i] = nums[i];
            }else{
                preMax[i] = preMax[i-1];
            }
        }
        for(int i = len - 2; i > 0; --i){
            if(nums[i] < postMin[i+1]){
                postMin[i] = nums[i];
            }else{
                postMin[i] = postMin[i + 1];
            }
        }
        for(int i = 1; i < len - 1; ++i){
            if(nums[i] > preMax[i-1] && nums[i] < postMin[i+1]){
                ans += 2;
            }else if(nums[i] > nums[i-1] && nums[i] < nums[i+1]){
                ++ans;
            }
        }
        return ans;
    }
}

美丽值1和0的情况好解决，主要是美丽值为2时需要比较数组左边和右边的最值。
既然需要比较最值，我用两个数组分别存储每一位左边的最大值和右边的最小值。因为第i位只要大于左边的最大值，那么就大于左边的所有值，右边同理。
为了计算最值，用了两个循环，然后再用一个循环来计算漂亮值。
所用的时间复杂度较高。应该有更好的做法。

推荐做法

class Solution {
    public int sumOfBeauties(int[] nums) {
        int n = nums.length;
        int[] sufMin = new int[n]; // 后缀最小值
        sufMin[n - 1] = nums[n - 1];
        for (int i = n - 2; i > 1; i--) {
            sufMin[i] = Math.min(sufMin[i + 1], nums[i]);
        }

        int ans = 0;
        int preMax = nums[0]; // 前缀最大值
        for (int i = 1; i < n - 1; i++) {
            int x = nums[i];
            // 此时 preMax 表示 [0, i-1] 中的最大值
            if (preMax < x && x < sufMin[i + 1]) {
                ans += 2;
            } else if (nums[i - 1] < x && x < nums[i + 1]) {
                ans++;
            }
            // 更新后 preMax 表示 [0, i] 中的最大值
            preMax = Math.max(preMax, x);
        }
        return ans;
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/sum-of-beauty-in-the-array/solutions/1006001/qian-zhui-zui-da-zhi-hou-zhui-zui-xiao-z-h9qz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

在计算最大值的同时计算漂亮值，可以节省一个循环的时间。