题目描述
给你一个下标从 0 开始的整数数组 nums
。
请你从所有满足 i < j < k
的下标三元组 (i, j, k)
中,找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数,则返回 0
。
下标三元组 (i, j, k)
的值等于 (nums[i] - nums[j]) * nums[k]
。
样例
输入:nums = [12,6,1,2,7]
输出:77
解释:下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77。
可以证明不存在值大于 77 的有序下标三元组。
输入:nums = [1,10,3,4,19]
输出:133
解释:下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133。
可以证明不存在值大于 133 的有序下标三元组。
输入:nums = [1,2,3]
输出:0
解释:唯一的下标三元组 (0, 1, 2) 的值是一个负数,(nums[0] - nums[1]) * nums[2] = -3。
因此,答案是 0。
限制
3 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
算法
(前后缀分解) $O(n)$
- 预处理求出每个位置后缀的最大值和最小值。
- 遍历每个前缀,同时维护当前的最大值和最小值。对于当前位置的数字,将其作为 $j$,分别使用前缀最小值与后缀最小值,前缀最大值与后缀最大值更新答案。
时间复杂度
- 遍历数组两次,时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储后缀最大值和最小值。
C++ 代码
#define LL long long
class Solution {
public:
LL maximumTripletValue(vector<int>& nums) {
const int n = nums.size();
vector<int> minsuf(n), maxsuf(n);
minsuf[n - 1] = maxsuf[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
minsuf[i] = min(minsuf[i + 1], nums[i]);
maxsuf[i] = max(maxsuf[i + 1], nums[i]);
}
int minpre = nums[0], maxpre = nums[0];
LL ans = 0;
for (int i = 1; i < n - 1; i++) {
ans = max(ans, (LL)(minpre - nums[i]) * minsuf[i + 1]);
ans = max(ans, (LL)(maxpre - nums[i]) * maxsuf[i + 1]);
minpre = min(minpre, nums[i]);
maxpre = max(maxpre, nums[i]);
}
return ans;
}
};