力扣：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 <= 1051 <= nums[i] <= 105
题解：
-
初始化
left_max和right_min数组：left_max[i]记录从nums[0]到nums[i-1]中的最大值。right_min[i]记录从nums[i+1]到nums[n-1]中的最小值。
-
填充
left_max数组：- 从左到右遍历数组，记录每个位置左侧的最大值。
-
填充
right_min数组：- 从右到左遍历数组，记录每个位置右侧的最小值。
-
计算美丽值：
遍历数组nums，对于每个1 <= i <= n-2的位置，根据规则计算美丽值并累加到结果中。
class Solution {
public:
int sumOfBeauties(vector<int>& nums) {
int n = nums.size();
if (n < 3) return 0; // 保证数组长度至少为3
// 初始化 left_max 和 right_min 数组
vector<int> left_max(n, 0);
vector<int> right_min(n, 0);
// 填充 left_max 数组
left_max[0] = nums[0];
for (int i = 1; i < n; ++i) {
left_max[i] = max(left_max[i-1], nums[i]);
}
// 填充 right_min 数组
right_min[n-1] = nums[n-1];
for (int i = n-2; i >= 0; --i) {
right_min[i] = min(right_min[i+1], nums[i]);
}
int result = 0;
// 计算每个下标的美丽值
for (int i = 1; i < n - 1; ++i) {
if (left_max[i-1] < nums[i] && nums[i] < right_min[i+1]) {
result += 2;
} else if (nums[i-1] < nums[i] && nums[i] < nums[i+1]) {
result += 1;
}
}
return result;
}
};
官方题解：
思路与算法
美丽值只有三种取值：
对于取值为 2 的情况，我们总共需要两次遍历，第一次遍历判断某个值是否严格大于前面所有的值，第二次倒序遍历判断某个值是否严格小于后面所有的值。
对于取值为 1 的情况，在第二次遍历时排除取值为 2 后判断即可。
对于取值为 0 的情况，不需要特殊判断。
对于取值为 2 的情况，在第一次遍历的过程中维护一个前缀最大值，若当前值严格大于该前缀最大值，则标记当前值；接着在第二次遍历的过程中维护一个后缀最小值，若当前值严格小于该后缀最小值并且当前值在第一次遍历时被标记过，则答案累加 2。
代码
作者：力扣官方题解
链接：https://leetcode.cn/problems/sum-of-beauty-in-the-array/solutions/3088657/shu-zu-mei-li-zhi-qiu-he-by-leetcode-sol-y8ej/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public:
int sumOfBeauties(vector<int>& nums) {
int n = nums.size();
vector<int> state(n);
int pre_max = nums[0];
for (int i = 1; i < n - 1; i++) {
if (nums[i] > pre_max) {
state[i] = 1;
pre_max = nums[i];
}
}
int suf_min = nums[n - 1];
int res = 0;
for (int i = n - 2; i > 0; i--) {
if (state[i] && nums[i] < suf_min) {
res += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
res += 1;
}
suf_min = min(suf_min, nums[i]);
}
return res;
}
};
省流：条件一是 “所有” ： 前缀最大 < 当前 nums[i] < 后缀最小