【LetMeFly】2012.数组美丽值求和：前缀和
力扣题目链接：https://leetcode.cn/problems/sum-of-beauty-in-the-array/
给你一个下标从 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
解题方法：前缀和
如何快速判断$nums[0]$到$nums[i - 1]$是否都小于$nums[i]$？可以利用前缀思想，遍历一遍数组并将$nums[0]$到$nums[i - 1]$的最大值存入$mx[i - 1]$数组中。
同理，可使用$mn[i + 1]$代表$nums[i + 1]$到$nums[len(nums) - 1]$的最小值。
这样，只需要遍历一遍数组，就能统计出来每一个$i$的得分了。
- 时间复杂度$O(len(nums))$
- 空间复杂度$O(len(nums))$
优化：前缀数组可以使用一个变量在遍历的过程中维护（见Golang版本）。
AC代码
C++
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
|
class Solution {
public:
int sumOfBeauties(vector<int>& nums) {
vector<int> M(nums.size()), m(nums.size());
int now = 0;
for (int i = 0; i < nums.size(); i++) {
M[i] = now = max(now, nums[i]);
}
now = 1000000;
for (int i = nums.size() - 1; i >= 0; i--) {
m[i] = now = min(now, nums[i]);
}
int ans = 0;
for (int i = 1; i < nums.size() - 1; i++) {
if (M[i - 1] < nums[i] && nums[i] < m[i + 1]) {
ans += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
ans++;
}
}
return ans;
}
};
|
Python
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
| '''
Author: LetMeFly
Date: 2025-03-11 14:04:02
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-11 14:07:14
'''
from typing import List
class Solution:
def sumOfBeauties(self, nums: List[int]) -> int:
mx = [0] * len(nums)
mn = [0] * len(nums)
now = 0
for i in range(len(nums)):
mx[i] = now = max(now, nums[i])
now = 1000000
for i in range(len(nums) - 1, -1, -1):
mn[i] = now = min(now, nums[i])
ans = 0
for i in range(1, len(nums) - 1):
if mx[i - 1] < nums[i] < mn[i + 1]:
ans += 2
elif nums[i - 1] < nums[i] < nums[i + 1]:
ans += 1
return ans
|
Java
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
|
class Solution {
public int sumOfBeauties(int[] nums) {
int[] mx = new int[nums.length];
int[] mn = new int[nums.length];
int now = 0;
for (int i = 0; i < nums.length; i++) {
mx[i] = now = Math.max(now, nums[i]);
}
for (int i = nums.length - 1; i >= 0; i--) {
mn[i] = now = Math.min(now, nums[i]);
}
int ans = 0;
for (int i = 1; i < nums.length - 1; i++) {
if (mx[i - 1] < nums[i] && nums[i] < mn[i + 1]) {
ans += 2;
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
ans++;
}
}
return ans;
}
}
|
Go
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
|
package main
func sumOfBeauties(nums []int) (ans int) {
mn := make([]int, len(nums))
now := 100000
for i := len(nums) - 1; i >= 0; i-- {
now = min(now, nums[i])
mn[i] = now
}
now = nums[0]
for i := 1; i < len(nums) - 1; i++ {
if now < nums[i] && nums[i] < mn[i + 1] {
ans += 2
} else if nums[i - 1] < nums[i] && nums[i] < nums[i + 1] {
ans++
}
now = max(now, nums[i])
}
return
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源