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

题目

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

实现

一、贪心算法

思路：由公式 $$\begin{gathered} ( \\ nums[i]-nums[j])\ast \\ nums[k] \end{gathered}$$ 可知，nums[i] 取区间 [0,j) 内的最大值时，$$\begin{gathered} ( \\ nums[i]-nums[j])\ast \\ nums[k] \end{gathered}$$ 最大。使用两层循环分别枚举 k 和 j，同时使用 m 维护 [0,j) 的最大值，返回所有 $$\begin{gathered} ( \\ nums[i]-nums[j])\ast \\ nums[k] \end{gathered}$$ 的最大值（若所有值都为负数，则返回 0）。

var maximumTripletValue = function (nums) {
    let n = nums.length;
    let res = 0;
    for (let k = 2; k < n; k++) {
        let m = nums[0]
        for (let j = 1; j < k; j++) {
            res = Math.max(res, (m - nums[j]) * nums[k]);
            m = Math.max(m, nums[j]);
        }
    }
    return res;
};

复杂度分析

• 时间复杂度：O(n2)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(1)。

二、优化：贪心 + 前后缀数组

思路：当 j 值固定时，$nums[i]$ 和 $nums[k]$ 分别取最大值时三元组最大。维护前后缀数组 $leftMax[j]$ 和 $rightMax[j]$，依次枚举 j 来计算三元组最大值

var maximumTripletValue = function (nums) {
    const n = nums.length;
    const leftMax = new Array(n).fill(0)
    const rightMax = new Array(n).fill(0)
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1])
        rightMax[n - 1 - i] = Math.max(rightMax[n - i], nums[n - i])
    }
    let res = 0;
    for (let j = 1; j < n - 1; j++) {
        res = Math.max(res, (leftMax[j] - nums[j]) * rightMax[j])
    }
 
    return res;
};

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(n)。