[LeetCode] 每日一题 2873. 有序三元组中的最大值 I（前后缀数组 + 贪心优化）
题目链接
题目描述
给你一个下标从 0 开始的整数数组 nums 。
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。
示例输入
示例 1
输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以证明不存在值大于 77 的有序下标三元组。示例 2
输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值大于 133 的有序下标三元组。 示例 3
输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。提示
3 <= nums.length <= 1001 <= nums[i] <= 10^6
解题思路
这道题虽然在 LeetCode 上标注为简单题，但其中的优化思路很值得思考。核心在于如何高效地选择 (i, j, k) 使得 (nums[i] - nums[j]) * nums[k] 最大化
方法 1：前后缀数组
我们可以预处理前后缀最大值，避免暴力遍历：
维护
preMax[i]，表示nums在i之前的最大元素值维护
suffixMax[i]，表示nums在i之后的最大元素值遍历
j作为中间元素，计算(preMax[j] - nums[j]) * suffixMax[j]，并更新最大值
代码实现
class Solution {
public long maximumTripletValue(int[] nums) {
long ans = 0;
int n = nums.length;
int[] preMax = new int[n], suffixMax = new int[n];
for (int i = 1; i < n; i++) {
preMax[i] = Math.max(preMax[i - 1], nums[i - 1]);
suffixMax[n - i - 1] = Math.max(suffixMax[n - i], nums[n - i]);
}
for (int j = 1; j < n - 1; j++) {
ans = Math.max(ans, (long)(preMax[j] - nums[j]) * suffixMax[j]);
}
return ans;
}
}这个方法的时间复杂度是 O(n)，但额外使用了 O(n) 的空间来存储 preMax 和 suffixMax
方法 2：贪心优化
如果我们只关心 preMax[j] 和 suffixMax[j]，我们可以直接用两个变量动态维护：
iMax：记录nums[i]的最大值（遍历过程中维护）dMax：记录nums[i] - nums[j]的最大值
代码实现
class Solution {
public long maximumTripletValue(int[] nums) {
long ans = 0;
int iMax = 0;
int dMax = 0;
for (int num : nums) {
ans = Math.max(ans, (long)dMax * num);
dMax = Math.max(dMax, iMax - num);
iMax = Math.max(iMax, num);
}
return ans;
}
}复杂度分析
方法 1（前后缀数组）：
时间复杂度：
O(n)（两次遍历）空间复杂度：
O(n)（额外的前缀和后缀数组）
方法 2（贪心优化）：
时间复杂度：
O(n)（单次遍历）空间复杂度：
O(1)（只用两个变量）
总结
这道题的暴力解法 O(n^3) 绝对不可取，我们可以先用前后缀数组优化到 O(n)，然后进一步用贪心算法优化到 O(1) 的空间复杂度。这种逐步优化的思维方式在日常刷题和开发中非常重要🤗
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。