【LeetCode】数组美丽值求和 Java 题解

作者：Albert

2022 年 7 月 13 日
本文字数：1188 字
阅读完需：约 4 分钟

题目描述

给你一个下标从 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
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/sum-of-beauty-in-the-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是数组题目，题目自定义了一种美丽值的算法，我们需要求出 nums[i] 的美丽值，累加求和之后就是结果。
计算美丽值的规则比较清晰，我们可以直接按照规则，实现朴素算法。朴素算法有较多的重复计算，时间复杂度比较高，不能通过全部用例。
我们需要减少重复计算，通过朴素算法，更好的理解了题目含义。中间的数满足大于左边所有数，并且小于右边所有数，即可+2。可以使用两个变量分别记录左边的最大值和右边的最小值。然后设置 boolean[] temp 数组，判断当前的 nums[i] 与左边最大数，右边最小数的关系，同时动态更新最值问题。当不满足 +2 的条件时候，在判断时候是否满足 +1 的条件。具体代码实现如下，供参考。

通过代码

class Solution {    public int sumOfBeauties(int[] nums) {        int ans = 0;        int n = nums.length;        int leftMax = nums[0];        int rightMin = nums[n - 1];        boolean[] temp = new boolean[n];
        for (int i = 1; i < n - 1; i++) {            if (nums[i] > leftMax) {                temp[i] = true;                leftMax = nums[i];            }        }
        for (int i = n - 2; i >= 1; i--) {            if (nums[i] < rightMin) {                rightMin = nums[i];            } else {                temp[i] = false;            }        }        for (int i = 1; i <= n - 2; ++i) {            if (temp[i]) {                ans += 2;            } else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {                ans += 1;            }        }        return ans;    }}