Medium

题目描述

给你一个下标从 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 。
可以证明不存在值更大的有序三元组。

示例 2：

输入：nums = [1,10,3,4,19]
输出：133
解释：三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值更大的有序三元组。

示例 3：

输入：nums = [1,2,3]
输出：0
解释：唯一的有序三元组 (0, 1, 2) 的值是负数 (nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。

提示：

  • 3 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

解题思路

解题思路

这道题要求找到满足 i < j < k 条件的三元组，使得 (nums[i] - nums[j]) * nums[k] 的值最大。

方法一：暴力法 O(n³)

枚举所有可能的三元组，计算每个三元组的值并取最大值。但由于数据规模较大，这种方法会超时。

方法二：前缀后缀最值优化 O(n) - 推荐

观察表达式 (nums[i] - nums[j]) * nums[k]，我们可以发现：

  • 要使表达式最大，需要 nums[i] 尽可能大，nums[j] 尽可能小，nums[k] 尽可能大
  • 对于固定的 j，最优的 i 应该是 j 左边的最大值，最优的 k 应该是 j 右边的最大值

因此我们可以：

  1. 预处理前缀最大值数组 prefix_max[i]，表示 nums[0] 到 nums[i] 的最大值
  2. 预处理后缀最大值数组 suffix_max[i]，表示 nums[i] 到 nums[n-1] 的最大值
  3. 对于每个可能的中间位置 j，计算 (prefix_max[j-1] - nums[j]) * suffix_max[j+1]

这样时间复杂度降低到 O(n)，空间复杂度为 O(n)。

方法三：一次遍历优化

实际上我们可以在一次遍历中完成计算，维护当前位置左边的最大值和右边的最大值，进一步优化空间复杂度。

代码实现

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix_max(n), suffix_max(n);
        
        // 计算前缀最大值
        prefix_max[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix_max[i] = max(prefix_max[i-1], nums[i]);
        }
        
        // 计算后缀最大值
        suffix_max[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffix_max[i] = max(suffix_max[i+1], nums[i]);
        }
        
        long long result = 0;
        for (int j = 1; j < n-1; j++) {
            long long value = (long long)(prefix_max[j-1] - nums[j]) * suffix_max[j+1];
            result = max(result, value);
        }
        
        return result;
    }
};

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 计算前缀最大值
        prefix_max = [0] * n
        prefix_max[0] = nums[0]
        for i in range(1, n):
            prefix_max[i] = max(prefix_max[i-1], nums[i])
        
        # 计算后缀最大值
        suffix_max = [0] * n
        suffix_max[n-1] = nums[n-1]
        for i in range(n-2, -1, -1):
            suffix_max[i] = max(suffix_max[i+1], nums[i])
        
        result = 0
        for j in range(1, n-1):
            value = (prefix_max[j-1] - nums[j]) * suffix_max[j+1]
            result = max(result, value)
        
        return result

public class Solution {
    public long MaximumTripletValue(int[] nums) {
        int n = nums.Length;
        int[] prefixMax = new int[n];
        int[] suffixMax = new int[n];
        
        // 计算前缀最大值
        prefixMax[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixMax[i] = Math.Max(prefixMax[i-1], nums[i]);
        }
        
        // 计算后缀最大值
        suffixMax[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffixMax[i] = Math.Max(suffixMax[i+1], nums[i]);
        }
        
        long result = 0;
        for (int j = 1; j < n-1; j++) {
            long value = (long)(prefixMax[j-1] - nums[j]) * suffixMax[j+1];
            result = Math.Max(result, value);
        }
        
        return result;
    }
}

var maximumTripletValue = function(nums) {
    const n = nums.length;
    const prefixMax = new Array(n);
    const suffixMax = new Array(n);
    
    // 计算前缀最大值
    prefixMax[0] = nums[0];
    for (let i = 1; i < n; i++) {
        prefixMax[i] = Math.max(prefixMax[i-1], nums[i]);
    }
    
    // 计算后缀最大值
    suffixMax[n-1] = nums[n-1];
    for (let i = n-2; i >= 0; i--) {
        suffixMax[i] = Math.max(suffixMax[i+1], nums[i]);
    }
    
    let result = 0;
    for (let j = 1; j < n-1; j++) {
        const value = (prefixMax[j-1] - nums[j]) * suffixMax[j+1];
        result = Math.max(result, value);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

相关题目