【leetcode】2012. 数组美丽值求和.md

题目描述

leetcode.cn/problems/…/description

思路

水题, 看题目看了半天, 第一个说的是前面所有的数都比中间的数小, 后面所有的数都比中间的数大.
直接前缀和求最大值, 后缀和求最小值即可.

代码

impl Solution {
    pub fn sum_of_beauties(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut pre: Vec<i32> = vec![0; nums.len()];
        let mut suf: Vec<i32> = vec![0; nums.len()];

        // 前缀和
        pre[0] = nums[0];
        for i in 1..nums.len() {
            pre.push(std::cmp::max(pre[i - 1], nums[i]));
        }
        // 后缀和
        suf[nums.len() - 1] = nums[nums.len() - 1];
        for i in (0..(nums.len() - 1)).rev() {
            suf[i] = std::cmp::min(suf[i + 1], nums[i]);
        }

        for i in 1..(nums.len() - 1) {
            if pre[i - 1] < nums[i] && nums[i] < suf[i + 1] {
                ans += 2;
            } else if nums[i - 1] < nums[i] && nums[i] < nums[i + 1] {
                ans += 1;
            }
        }

        ans
    }
}