LeetCode 题解工作台
数组美丽值求和
给你一个下标从 0 开始的整数数组 nums 。对于每个下标 i （ 1 ）， nums[i] 的 美丽值 等于： 2 ，对于所有 0 且 i ，满足 nums[j] 1 ，如果满足 nums[i - 1] ，且不满足前面的条件 0 ，如果上述条件全部不满足 返回符合 1 的所有 nums[i] 的…
1
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·driven
答案摘要
我们可以预处理出右侧最小值数组 ，其中 表示 中的最小值。 然后我们从左到右遍历数组 ，同时维护左侧最大值 。对于每个位置 ，我们判断 $l < nums[i] < right[i + 1]$ 是否成立，如果成立则将 累加至答案，否则判断 $nums[i - 1] < nums[i] < nums[i + 1]$ 是否成立，如果成立则将 累加至答案。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·driven 题型思路
题目描述
给你一个下标从 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
解题思路
方法一：预处理右侧最小值 + 遍历维护左侧最大值
我们可以预处理出右侧最小值数组 ，其中 表示 中的最小值。
然后我们从左到右遍历数组 ，同时维护左侧最大值 。对于每个位置 ，我们判断 是否成立，如果成立则将 累加至答案，否则判断 是否成立，如果成立则将 累加至答案。
遍历结束后即可得到答案。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def sumOfBeauties(self, nums: List[int]) -> int:
n = len(nums)
right = [nums[-1]] * n
for i in range(n - 2, -1, -1):
right[i] = min(right[i + 1], nums[i])
ans = 0
l = nums[0]
for i in range(1, n - 1):
r = right[i + 1]
if l < nums[i] < r:
ans += 2
elif nums[i - 1] < nums[i] < nums[i + 1]:
ans += 1
l = max(l, nums[i])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element is processed once with precomputed prefix and suffix arrays. Space complexity is O(n) due to storing the prefix maximums and suffix minimums for all elements. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate tries nested loops instead of prefix/suffix optimization.
- question_mark
Candidate misses strict versus adjacent comparison distinctions for beauty evaluation.
- question_mark
Candidate overlooks edge indices, focusing only on middle array elements.
常见陷阱
外企场景- error
Using O(n^2) nested loops leading to timeout on large arrays.
- error
Confusing beauty 2 with beauty 1 conditions and miscounting.
- error
Failing to precompute prefix/suffix arrays, recalculating maxima/minima repeatedly.
进阶变体
外企场景- arrow_right_alt
Compute sum of beauty for a sliding window within the array.
- arrow_right_alt
Modify beauty rules to consider k previous and next elements instead of immediate neighbors.
- arrow_right_alt
Calculate maximum possible total beauty for arrays with arbitrary integer ranges.