[LeetCode] 每日一题 2012. 数组美丽值求和

题目链接

https://leetcode.cn/problems/sum-of-beauty-in-the-array

题目描述

给你一个下标从 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^5

• 1 <= nums[i] <= 10^5

解题思路

这道题的核心思想是预处理出每个元素左侧的最大值和右侧的最小值，以便快速判断元素的美丽值。具体而言，我们可以使用 前缀最大值数组 和 后缀最小值数组，分别记录当前位置之前的最大值和之后的最小值。这样，我们只需一次遍历就可以确定 nums[i] 是否满足条件，从而计算出美丽值的总和。

对于每个 nums[i]：

1. 如果 nums[i] 在它左侧的所有数中是最大值，且在右侧的所有数中是最小值，则美丽值为 2

2. 如果 nums[i] 仅比相邻的 nums[i-1] 和 nums[i+1] 大，则美丽值为 1

3. 否则，美丽值为 0

由于构造前缀最大值和后缀最小值的过程都是线性时间复杂度，最终的计算过程也只需要一次遍历，因此整体效率较高。

代码实现

class Solution {
    public int sumOfBeauties(int[] nums) {
        int n = nums.length;
        int ans = 0;
        int[] max = new int[n], min = new int[n];
        max[0] = Integer.MIN_VALUE;
        min[n - 1] = Integer.MAX_VALUE;
        // 计算前缀最大值和后缀最小值
        for (int i = 1; i < n; i++) {
            max[i] = Math.max(max[i - 1], nums[i - 1]);
            min[n - i - 1] = Math.min(min[n - i], nums[n - i]);
        }
        for (int i = 0; i < n; i++) {
            if (i == 0 || i == n - 1) {
                continue;
            }
            if (nums[i] > max[i] && nums[i] < min[i]) {
                ans += 2;
            } else if (nums[i] > nums[i - 1] && nums[i] < nums[i + 1]) {
                ans += 1;
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度: O(n)，其中 n 是数组长度。我们需要两次遍历来计算前缀最大值和后缀最小值，再进行一次遍历判断美丽值，总体仍然是 O(n)

• 空间复杂度: O(n)，由于额外使用了两个数组 max 和 min 来存储前缀最大值和后缀最小值

总结

这道题虽然看起来是直接遍历判断条件，但实际上用到了 前缀最大值 和 后缀最小值 的预处理方式，使得查找的效率大大提高。相比暴力解法，我们避免了在每次判断时都遍历整个数组，从 O(n^2) 降到了 O(n)。在实现过程中，需要注意遍历方向，尤其是 min 数组的构造是 从右向左 进行的，这一点容易忽略

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。