算法面试题深度解析：LeetCode 2012.数组元素的美丽值求和盘算与多方案对比 ...

算法面试题深度解析：LeetCode 2012.数组元素的美丽值求和盘算与多方案对比

原题

给你一个下标从 0 开始的整数数组 nums 。对于每个下标 i（1 <= i <= nums.length - 2），nums 的 美丽值 等于：
2，对于所有 0 <= j < i 且 i < k <= nums.length - 1 ，满足 nums[j] < nums < nums[k]
1，假如满足 nums[i - 1] < nums < nums[i + 1] ，且不满足前面的条件
0，假如上述条件全部不满足
返回符合 1 <= i <= nums.length - 2 的所有 nums 的 美丽值的总和 。
示例 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
  

标题描述

给定一个下标从0开始的整数数组 nums，要求盘算所有中心元素 nums（1 ≤ i ≤ nums.length-2）的美丽值总和。美丽值定义如下：

• 2分：所有左侧元素 < nums 且所有右侧元素 > nums；
  
• 1分：不满足2分条件，但满足 nums[i-1] < nums < nums[i+1]；
  
• 0分：其他环境。
  

<hr> 方案一：预处置惩罚前缀与后缀数组

焦点思路

• 前缀最大值数组 maxLeft：记录每个位置左侧的最大值。
  
• 后缀最小值数组 minRight：记录每个位置右侧的最小值。
  
• 遍历判断：联合两个数组快速判断每个元素的美丽值条件。
  

1. public class Solution {
2.    
3.     public int sumOfBeauties(int[] nums) {
4.    
5.         int n = nums.length;
6.         int[] maxLeft = new int[n], minRight = new int[n];
7.         maxLeft[0] = nums[0];
8.         minRight[n-1] = nums[n-1];
9.         
10.         for (int i = 1; i < n; i++)
11.             maxLeft[i] = Math.max(max

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。