2012 数组美丽值求和

· 2025-3-11   · 次阅读   · 字数统计: 170字   · 阅读时长≈ 1分钟

  · 算法题解   · LeetCode

题目链接

2012. 数组美丽值求和

分析

分别求出数组的前缀最大值和后缀最小值，遍历进行比较即可

代码实现

class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        int n = nums.size();
        vector<int> suf_min(n);
        suf_min[n - 1] = nums[n - 1];
        for(int i = n - 2; i > 1; --i) {
            suf_min[i] = min(suf_min[i + 1], nums[i]);
        }

        int ans = 0;
        int pre_max = nums[0];
        for(int i = 1; i < n - 1; ++i) {
            if(pre_max < nums[i] && nums[i] < suf_min[i + 1])
                ans += 2;
            else if(nums[i - 1] < nums[i] && nums[i] < nums[i + 1])
                ans++;
    
            pre_max = max(pre_max, nums[i]);
        }
  
        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$