leetcode 2873. 有序三元组中的最大值 I

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

题目描述

[2873] 有序三元组中的最大值 I

• https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-i/description

给你一个下标从 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

题目剖析&信息挖掘

由于数据较小，可以使用暴力枚举解决。

更进一步可能对公式进行分析

解题思路

方法一 暴力枚举法

思路

直接枚举，并判断大小

注意

• 计算时要用long long类型

复杂度

• 时间复杂度：O(n^3)
• 空间复杂度：O(n)

代码实现

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

方法二 公式拆分+动态规划

思路

可以考虑枚举 k, 然后去寻找 nums[i]-nums[j] (i<j<k) 的最大值。

那么，问题就转化为给定k 查寻nums[i]-nums[j] (i<j<k) 的最大值。

可以维护一个premax数组，premax[x] 代表nums[i]-nums[j] (i<j<=x) 的最大值。

递推公式

premax[0]=0,

premax[x] = max(max(nums[0…x-1])-nums[x], premax[x-1]).

注意

• 计算时要用long long类型

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

代码实现

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        long long res = 0;        
        vector<long long> premax(nums.size(), 0);
        int maxNum = 0;
        for(int i=0;i<nums.size();++i) {
            if(maxNum - nums[i]>0) premax[i] = maxNum - nums[i];
            if(i>1) premax[i] = max(premax[i], premax[i-1]);

            maxNum = max(maxNum, nums[i]);
        }
        for(int i=2;i<nums.size();++i) {
            if(premax[i-1]==0)continue;
            res = max(res, 1LL * nums[i]*premax[i-1]);
        }

        return res;
    }
};

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。