您的位置:首页 > 财经 > 金融 > 潍坊今日头条新闻_软件技术职业_关键路径_杨谦教授编的营销课程

潍坊今日头条新闻_软件技术职业_关键路径_杨谦教授编的营销课程

2025/3/18 17:39:39 来源:https://blog.csdn.net/2301_79218588/article/details/146191886  浏览:    关键词:潍坊今日头条新闻_软件技术职业_关键路径_杨谦教授编的营销课程
潍坊今日头条新闻_软件技术职业_关键路径_杨谦教授编的营销课程

给你一个下标从 0 开始的整数数组 nums 。对于每个下标 i1 <= 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 <= 105
  • 1 <= nums[i] <= 105

 题解:

  1. 初始化 left_maxright_min 数组

    • left_max[i] 记录从 nums[0] 到 nums[i-1] 中的最大值。
    • right_min[i] 记录从 nums[i+1] 到 nums[n-1] 中的最小值。
  2. 填充 left_max 数组

    • 从左到右遍历数组,记录每个位置左侧的最大值。
  3. 填充 right_min 数组

    • 从右到左遍历数组,记录每个位置右侧的最小值。
  4. 计算美丽值

    遍历数组 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] < 后缀最小

 

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com