有序三元组中的最大值 I

难度: Easy

给你一个下标从 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 <= 100
1 <= nums[i] <= 10⁶

Submission

运行时间: 26 ms

内存: 16.0 MB

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        suf_max = [0] * (n + 1)
        for i in range(n - 1, 1, -1):
            suf_max[i] = max(suf_max[i + 1], nums[i])
        ans = pre_max = 0
        for j, x in enumerate(nums):
            ans = max(ans, (pre_max - x) * suf_max[j + 1])
            pre_max = max(pre_max, x)
        return ans

Explain

该题解采用了前缀最大值和后缀最大值的方法。首先，通过一次从后向前的遍历构建一个后缀最大值数组`suf_max`，该数组在每个位置i存储了从i到数组末尾的最大值。随后，在一次从前向后的遍历中，使用一个变量`pre_max`来记录从数组开始到当前位置的最大值，然后对于每个位置j，计算`(pre_max - nums[j]) * suf_max[j + 1]`，并更新结果`ans`为所有可能组合中的最大值。这种方法有效地利用了动态规划的思想，通过记录前面的计算结果来避免重复计算，从而优化了时间复杂度。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums) # 获取数组长度
        suf_max = [0] * (n + 1) # 初始化后缀最大值数组
        for i in range(n - 1, 1, -1):
            suf_max[i] = max(suf_max[i + 1], nums[i]) # 从后向前填充后缀最大值数组
        ans = pre_max = 0 # 初始化答案和前缀最大值
        for j, x in enumerate(nums):
            ans = max(ans, (pre_max - x) * suf_max[j + 1]) # 计算所有可能的下标三元组的最大值
            pre_max = max(pre_max, x) # 更新前缀最大值
        return ans # 返回最大的下标三元组的值

Explore

后缀最大值数组`suf_max[i]`定义为从索引i到数组末尾的最大值。如果从后向前计算，可以确保每个位置i的值是基于i+1的值和当前位置的值计算得到的，这样可以一次遍历就完成数组的填充。反之，若从前向后计算，则每次更新suf_max[i]都需要重新检查后面所有元素，导致效率较低。

在计算最大三元组值时，关键在于最大化`(pre_max - nums[j]) * suf_max[j + 1]`这个表达式。这里`pre_max`是截至当前元素之前的最大值，而`suf_max[j + 1]`是从j+1至数组末尾的最大值。nums[j]作为中间元素，其值直接参与计算，无需考虑其他属性，因为我们已经通过`pre_max`和`suf_max[j + 1]`保证了最大值的计算覆盖所有可能的最大和最小差异组合。

数组`suf_max`的大小是`n+1`以便处理边界情况，特别是当遍历到数组的最后一个元素时。suf_max的最后一个元素`suf_max[n]`通常设置为一个很小的值或初始化值（如0），这样可以确保在计算`j = n-1`时，`suf_max[j + 1]`有定义且不会影响结果的正确性。

如果数组中的所有元素都相同，那么`pre_max`和`suf_max[j + 1]`的值也将与`nums[j]`相同。因此，`(pre_max - nums[j]) * suf_max[j + 1]`的计算结果为0。这意味着无论数组中的元素是什么，输出结果都将是0。这符合题目要求，因为没有任何三元组的组合能产生非零的`(pre_max - nums[j]) * suf_max[j + 1]`值。