蓝桥每日打卡--数组美丽值求和
#蓝桥#JAVA#数组美丽值求和
题目描述
给你一个下标从 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
解题思路
通过两次遍历数组来确定每个元素的美丽值。
第一次遍历：从左至右遍历数组，记录每个元素左侧的最大值。若当前元素大于左侧最大值，则标记该元素可能有美丽值 2。
第二次遍历：从右至左遍历数组，记录每个元素右侧的最小值。结合第一次遍历的标记，判断当前元素是否满足美丽值为 2 的条件；若不满足，再判断是否满足美丽值为 1 的条件。累加所有元素的美丽值得到最终结果。
class Solution {
public int sumOfBeauties(int[] nums) {
int n = nums.length;
// 创建一个长度为 n 的数组 state，用于标记每个元素是否可能有美丽值 2
int[] state = new int[n];
// 初始化 pre_max 为数组的第一个元素，用于记录当前元素左侧的最大值
int pre_max = nums[0];
// 从第二个元素开始遍历数组，直到倒数第二个元素
for (int i = 1; i < n - 1; i++) {
// 如果当前元素大于左侧最大值
if (nums[i] > pre_max) {
// 标记该元素可能有美丽值 2
state[i] = 1;
// 更新左侧最大值为当前元素
pre_max = nums[i];
}
}
// 初始化 suf_min 为数组的最后一个元素，用于记录当前元素右侧的最小值
int suf_min = nums[n - 1];
// 初始化结果变量 res 为 0，用于累加所有元素的美丽值
int res = 0;
// 从倒数第二个元素开始遍历数组，直到第二个元素
for (int i = n - 2; i > 0; i--) {
// 如果该元素被标记为可能有美丽值 2，并且小于右侧最小值
if (state[i] == 1 && nums[i] < suf_min) {
// 该元素的美丽值为 2，累加到结果中
res += 2;
}
// 如果不满足美丽值为 2 的条件，判断是否满足美丽值为 1 的条件
else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
// 该元素的美丽值为 1，累加到结果中
res += 1;
}
// 更新右侧最小值为当前元素和之前右侧最小值中的较小值
suf_min = Math.min(suf_min, nums[i]);
}
// 返回所有元素的美丽值总和
return res;
}
}