[LeetCode] 每日一题 2874. 有序三元组中的最大值 II（与昨天思路一致）
题目链接
题目描述
给你一个下标从 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 <= 10^51 <= nums[i] <= 10^6
解题思路
今天的题目和昨天的题目完全相同，唯一的区别是数据范围变大了，这意味着暴力 O(n^3) 遍历的方式彻底不可行。不过，昨天的优化思路仍然适用，因此我们可以直接沿用之前的前后缀数组法和贪心法。
在昨天的解法中，我们采用了两种不同的枚举方式：
前后缀数组法：枚举
j，并利用preMax[i]（i之前的最大值）和suffixMax[k]（k之后的最大值）进行计算。贪心法：枚举
k，动态维护iMax（历史最大nums[i]）和dMax（历史最大nums[i] - nums[j]），用更少的空间完成计算。
方法 1：前后缀数组
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;
}
}思路：
preMax[i]记录nums在i之前的最大值，即nums[i]作为j时，它的最大i值是多少。suffixMax[i]记录nums在i之后的最大值，即nums[j]作为k时，它的最大k值是多少。最终复杂度
O(n)，但需要O(n)额外空间。
方法 2：贪心优化
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;
}
}思路：
枚举
k（从左到右遍历nums），同时维护：iMax（历史最大nums[i]）dMax（历史最大nums[i] - nums[j]）
这样，我们可以在
O(1)额外空间内完成前后缀计算，使得时间复杂度仍为O(n)，空间复杂度降为O(1)🚀
复杂度分析
方法 1（前后缀数组）：
时间复杂度：
O(n)（两次遍历）空间复杂度：
O(n)（额外的前缀和后缀数组）
方法 2（贪心优化）：
时间复杂度：
O(n)（单次遍历）空间复杂度：
O(1)（只用两个变量）
总结
今天的题目只是数据范围更大了，但核心思路与昨天完全相同
如果想使用
O(n)空间，前后缀数组法依然适用贪心算法进一步优化到
O(1)空间，适用于更大规模的nums
对于这类三元组问题，找到合适的枚举方式是关键，能决定解法的复杂度
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。