LeetCode每日一题(2012. Sum of Beauty in the Array)

You are given a 0-indexed integer array nums. For each index i (1 <= i <= nums.length - 2) the beauty of nums[i] equals:

2, if nums[j] < nums[i] < nums[k], for all 0 <= j < i and for all i < k <= nums.length - 1.
1, if nums[i - 1] < nums[i] < nums[i + 1], and the previous condition is not satisfied.
0, if none of the previous conditions holds.
Return the sum of beauty of all nums[i] where 1 <= i <= nums.length - 2.

Example 1:

Input: nums = [1,2,3]
Output: 2

Explanation: For each index i in the range 1 <= i <= 1:

• The beauty of nums[1] equals 2.

Example 2:

Input: nums = [2,4,6,4]
Output: 1

Explanation: For each index i in the range 1 <= i <= 2:

• The beauty of nums[1] equals 1.
• The beauty of nums[2] equals 0.

Example 3:

Input: nums = [3,2,1]
Output: 0

Explanation: For each index i in the range 1 <= i <= 1:

• The beauty of nums[1] equals 0.

Constraints:

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 105

---

这题的要点是别想复杂了， 题目怎么说的怎么做就好， 别想着整花活。

我们建立两个数组 prefix 和 suffix 使得 prefix[i]为 nums[i]左侧的最大值, suffix[i]为 nums[i]右侧的最小值， 这样如果 prefix[i-1] < nums[i] < suffix[i+1], 则我们符合第一种情况， 分值+2, 如果不符合这一条件， 我们则退而求其次， 检查 nums[i-1] < nums[i] < nums[i+1], 如果成立则符合第二种情况， 分值+1, 如果这两种都不符合则分值+0

---

impl Solution {
    pub fn sum_of_beauties(nums: Vec<i32>) -> i32 {
        let prefix: Vec<i32> = nums
            .iter()
            .scan(0, |max, n| {
                *max = (*max).max(*n);
                Some(*max)
            })
            .collect();
        let mut suffix: Vec<i32> = nums
            .iter()
            .rev()
            .scan(i32::MAX, |min, n| {
                *min = (*min).min(*n);
                Some(*min)
            })
            .collect();
        suffix.reverse();
        let mut ans = 0;
        for i in 1..nums.len() - 1 {
            if prefix[i - 1] < nums[i] && nums[i] < suffix[i + 1] {
                ans += 2;
                continue;
            }
            if nums[i - 1] < nums[i] && nums[i] < nums[i + 1] {
                ans += 1;
            }
        }
        ans
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33