有序三元组中的最大值 II

You are given a 0-indexed integer array nums.

Return the maximum value over all triplets of indices (i, j, k) such that i < j < k. If all such triplets have a negative value, return 0.

The value of a triplet of indices (i, j, k) is equal to (nums[i] - nums[j]) * nums[k].

 

Example 1:

Input: nums = [12,6,1,2,7]
Output: 77
Explanation: The value of the triplet (0, 2, 4) is (nums[0] - nums[2]) * nums[4] = 77.
It can be shown that there are no ordered triplets of indices with a value greater than 77. 

Example 2:

Input: nums = [1,10,3,4,19]
Output: 133
Explanation: The value of the triplet (1, 2, 4) is (nums[1] - nums[2]) * nums[4] = 133.
It can be shown that there are no ordered triplets of indices with a value greater than 133.

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: The only ordered triplet of indices (0, 1, 2) has a negative value of (nums[0] - nums[1]) * nums[2] = -3. Hence, the answer would be 0.

 

Constraints:

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 106

/*
 * 思路：我们可以使用Java Stream API来简化对三元组的遍历。
 * 由于Stream API不直接支持三重循环，我们可以利用IntStream来实现。
 */
import java.util.stream.IntStream;
public class Solution {
    public int maxTripletValue(int[] nums) {
        int n = nums.length;
        return IntStream.range(0, n - 2).boxed()
            .flatMap(i -> IntStream.range(i + 1, n - 1).boxed()
            .flatMap(j -> IntStream.range(j + 1, n).mapToObj(k -> (nums[i] - nums[j]) * nums[k])))
            .max(Integer::compare)
            .filter(val -> val > 0)
            .orElse(0);
    }
}

这个题解使用了一次遍历的方法。我们首先定义一个变量 preMax 来存储遍历过的元素中的最大值，定义一个变量 maxD 来存储遍历过的元素中 preMax 和当前元素差的最大值。在遍历过程中，我们首先计算当前元素与 maxD 的乘积，如果这个乘积大于之前的答案，则更新答案。然后，我们计算 preMax 与当前元素的差，如果这个差大于 maxD，则更新 maxD。最后，如果当前元素大于 preMax，则更新 preMax。这样，在遍历结束时，我们就能得到最大的三元组值。

O(n)

O(1)