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^6

解题思路

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

方法一：暴力枚举（推荐）

由于数组长度最多为 100，我们可以使用三重循环暴力枚举所有满足条件的三元组。对于每个三元组，计算其值并维护最大值。

具体步骤：

  1. 使用三重循环遍历所有满足 i < j < k 的三元组
  2. 计算当前三元组的值 (nums[i] - nums[j]) * nums[k]
  3. 维护最大值，注意如果所有值都是负数则返回 0

时间复杂度为 O(n³)，但由于 n ≤ 100，完全可以接受。

方法二：优化枚举

我们可以固定 k，然后在前面的元素中找到最大的 nums[i] - nums[j]（其中 i < j < k）。可以预处理每个位置之前的最大差值，将复杂度降为 O(n²)。

对于较大的数据规模，方法二更优，但本题数据量小，方法一已经足够。

代码实现

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        long long maxVal = 0;
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    long long val = (long long)(nums[i] - nums[j]) * nums[k];
                    maxVal = max(maxVal, val);
                }
            }
        }
        
        return maxVal;
    }
};

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        max_val = 0
        
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    val = (nums[i] - nums[j]) * nums[k]
                    max_val = max(max_val, val)
        
        return max_val

public class Solution {
    public long MaximumTripletValue(int[] nums) {
        int n = nums.Length;
        long maxVal = 0;
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    long val = (long)(nums[i] - nums[j]) * nums[k];
                    maxVal = Math.Max(maxVal, val);
                }
            }
        }
        
        return maxVal;
    }
}

var maximumTripletValue = function(nums) {
    const n = nums.length;
    let maxVal = 0;
    
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                const val = (nums[i] - nums[j]) * nums[k];
                maxVal = Math.max(maxVal, val);
            }
        }
    }
    
    return maxVal;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度暴力枚举优化枚举
时间复杂度O(n³)O(n²)
空间复杂度O(1)O(1)

注：由于题目约束 n ≤ 100，暴力枚举方法已经足够高效。

相关题目