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 <= 105
• 1 <= nums[i] <= 106

---

思路

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k]

我的思路就是找到nums[i]的最大值，nums[j]的最小值，nums[k]的最大值并且还要保证i<j<k。

这样就可以得出结果了，最开始我们固定j来找两边。

最后就是这样的：

1. 预处理后缀最大值数组：suffixMax[i] 表示从 i 到数组末尾的最大值。
2. 动态维护左边最大值：在遍历数组时，维护一个变量 leftMax 来记录当前元素左边的最大值。
3. 计算三元组值：对于每个中间元素 nums[j]，计算 (leftMax - nums[j]) * suffixMax[j + 1]，并更新全局最大值。

---

完整代码

class Solution {
    public long maximumTripletValue(int[] nums) {
        int n=nums.length;
        int[] lat=new int[n];

        //将所有右边最大的数找出来
        lat[n-1]=nums[n-1];
        for(int i=n-2;i>=0;i--)
            lat[i]=Math.max(lat[i+1],nums[i]);

        long res=0;
        int leftMax=nums[0];//左边最大值
        for(int j=1;j<n-1;j++){
            long ans=(long)(leftMax-nums[j])*lat[j+1];
            res=Math.max(res,ans);
            leftMax=Math.max(leftMax,nums[j]);
        }
        return res<0?0:res;
    }
}

---

代码详解

我觉得我还是有必要详细讲解一下这段代码，至少这方面的思想是很不错的！

//将所有右边最大的数找出来
lat[n-1]=nums[n-1];
for(int i=n-2;i>=0;i--)
	lat[i]=Math.max(lat[i+1],nums[i]);

来看这一段代码，

想象你有一排数字，比如：[12, 6, 1, 2, 7]。这段代码的任务是：为每个位置记录”从它开始往右看，能看到的最大的数字是多少”。

举个具体例子

以 [12, 6, 1, 2, 7] 为例：

1. 最后一个位置（第5个数字，数字7）：
   • 它右边没有数字了，所以它自己能看到的”往右最大的数字”就是自己：7
2. 倒数第二个位置（第4个数字，数字2）：
   • 往右看：先看到自己2，然后看到它右边的7
   • 最大的数字是 max(2,7)=7
3. 倒数第三个位置（第3个数字，数字1）：
   • 往右看：自己1，右边依次是2和7
   • 最大的数字是 max(1,7)=7（因为2和7中7更大）
4. 依此类推：
   • 第2个数字6：往右看最大的是max(6,7)=7
   • 第1个数字12：往右看最大的是max(12,7)=12

最终得到的结果

位置： 0   1   2   3   4
数值：[12, 6, 1, 2, 7]
结果：[12, 7, 7, 7, 7]

---

long res=0;
int leftMax=nums[0];//左边最大值
for(int j=1;j<n-1;j++){
	long ans=(long)(leftMax-nums[j])*lat[j+1];
	res=Math.max(res,ans);
	leftMax=Math.max(leftMax,nums[j]);
}

这段代码同理，就是找出左边的最大值，然后随便再把 (nums[i] - nums[j]) * nums[k] 求解一下。