力扣2012题：双指针解法详解
一、题目解读
力扣2012题要求计算数组中每个元素的"美丽值"总和。美丽值判定规则：
若元素严格大于左侧所有元素且严格小于右侧所有元素，得2分
若仅满足大于左邻元素且小于右邻元素，得1分
其余情况不得分
二、解题思路
通过左右双指针预处理技术：
左数组预处理：存储每个位置左侧最大值
右数组预处理：存储每个位置右侧最小值
并行校验：同时检查两种美丽值条件 该方法将O(n²)暴力解法优化为O(n)时间复杂度，空间复杂度O(n)
三、解题步骤拆解
初始化左右辅助数组
从左到右遍历构建left_max数组
从右到左遍历构建right_min数组
中间元素双重条件判断：
先校验严格大于左侧所有且小于右侧所有（2分条件）
再校验简单递增关系（1分条件）
四、完整代码实现
class Solution {
public:
int sumOfBeauties(vector<int>& nums) {
int n = nums.size();
vector<int> left_max(n), right_min(n);
// 预处理左边最大值
left_max[0] = nums[0];
for (int i = 1; i < n; ++i) {
left_max[i] = max(left_max[i-1], nums[i]);
}
// 预处理右边最小值
right_min[n-1] = nums[n-1];
for (int i = n-2; i >= 0; --i) {
right_min[i] = min(right_min[i+1], nums[i]);
}
int res = 0;
// 计算每个中间元素的美丽值
for (int i = 1; i < n-1; ++i) {
if (left_max[i-1] < nums[i] && nums[i] < right_min[i+1]) {
res += 2;
} else if (nums[i-1] < nums[i] && nums[i] < nums[i+1]) {
res += 1;
}
}
return res;
}
};五、算法总结
该解法展现了数组预处理技术的典型应用：
原创内容 转载请注明出处
