有序三元组中的最大值II-LeetCode

2874. 有序三元组中的最大值II

🎯 问题描述

描述：
给你一个下标从 0 开始的整数数组 nums。
请你找出并返回满足以下条件的三元组 $(i, j, k)$ 的最大值：

1. $0 \le i < j < k < n$
2. 三元组的值定义为：$(nums[i] - nums[j]) \times nums[k]$

如果所有三元组的值都小于 0，则返回 0。

说明：

• 这是一个枚举中间点结合前后缀极值预处理的问题。

• 核心策略：

  • 我们要最大化 $(nums[i] - nums[j]) \times nums[k]$。
  • 我们可以枚举中间的下标 $j$。
  • 当 $j$ 固定时，为了使结果最大，我们需要：
    1. 在 $j$ 的左侧（$i < j$）找到最大的 $nums[i]$，这样 $(nums[i] - nums[j])$ 才会尽可能大。
    2. 在 $j$ 的右侧（$k > j$）找到最大的 $nums[k]$，这样乘积的结果才会尽可能大（假设差值为正）。

• 预处理：通过预处理后缀最大值数组，我们可以 $O(1)$ 获取右侧最大值；通过动态维护前缀最大值，我们可以 $O(1)$ 获取左侧最大值。

• 示例：

• 示例 1：

输入：nums = [12,6,1,2,7]
输出：77
解释：
- 选择 i=0, j=2, k=4。
- nums[i]=12, nums[j]=1, nums[k]=7。
- 值 = (12 - 1) * 7 = 11 * 7 = 77。
- 这是最大值。

💻 解题思路

思路1：后缀最大值 + 前缀动态维护

核心逻辑

1. 预处理后缀最大值：
   • 构建数组 suf，其中 suf[i] 表示 nums[i...n-1] 范围内的最大值。
   • 这样，对于任意 $j$，其右侧最大的 $nums[k]$ 就是 suf[j+1]。
2. 动态维护前缀最大值：
   • 在遍历中间点 $j$ 时，用变量 pre 记录 nums[0...j-1] 范围内的最大值。
3. 枚举中间点 $j$：
   • 遍历 $j$ 从 $1$ 到 $n-2$。
   • 计算当前三元组的值：(pre - nums[j]) * suf[j+1]。
   • 更新全局最大值 ans。
   • 更新 pre，将 nums[j] 纳入左侧范围，供下一轮使用。
4. 处理负数结果：
   • 题目要求如果最大值小于 0 则返回 0。

代码实现

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 1. 预处理后缀最大值
        # suf[i] 表示 nums[i...n-1] 中的最大值
        suf = [-1] * n
        suf[-1] = nums[-1]
        for i in range(n - 2, -1, -1):
            suf[i] = max(suf[i + 1], nums[i])
        
        # 2. 遍历中间点 j，同时维护前缀最大值 pre
        pre = nums[0]  # pre 表示 nums[0...j-1] 中的最大值
        ans = float('-inf')
        
        for j in range(1, n - 1):
            # 3. 计算以 j 为中间点的三元组最大值
            # 左侧最大差值部分: pre - nums[j]
            # 右侧最大乘数部分: suf[j+1]
            num = (pre - nums[j]) * suf[j + 1]
            ans = max(ans, num)
            
            # 4. 更新前缀最大值
            pre = max(pre, nums[j])
            
        return ans if ans > 0 else 0

📊 性能分析

• 时间复杂度：$O(N)$
  • 其中 $N$ 是 nums 的长度。
  • 构建后缀数组需要一次遍历 $O(N)$。
  • 枚举中间点 $j$ 需要一次遍历 $O(N)$。
  • 总时间复杂度为 $O(N)$。
• 空间复杂度：$O(N)$
  • 需要一个长度为 $N$ 的数组 suf 来存储后缀最大值。

思考

1. 为什么只需要最大值？

   • 我们要最大化 $(A - B) \times C$。
   • 对于固定的 $B$ ($nums[j]$)，为了让结果最大：
     • 如果 $C > 0$，我们需要 $A$ 尽可能大。
     • 如果 $C < 0$，我们需要 $A$ 尽可能小（但这题里如果 $C$ 是负数，且 $A-B$ 是正数，结果就是负的，不如直接返回 0）。
   • 题目数据范围通常暗示我们寻找正向的最大收益。即使考虑负数情况，通常也是找极值。在这里，贪心策略是找左侧最大值和右侧最大值。

2. 后缀数组的构建：

   • suf[i] = max(suf[i+1], nums[i])。
   • 这保证了 suf[i] 包含了从 i 到末尾的所有元素的最大值。
   • 当我们检查 $j$ 时，右侧的范围是 $j+1$ 到 $n-1$，所以使用 suf[j+1]。

3. 前缀变量的更新：

   • pre 初始化为 nums[0]。
   • 在每次循环结束时，pre = max(pre, nums[j])。
   • 这保证了当循环到 $j+1$ 时，pre 存储的是 nums[0...j] 的最大值。

4. 边界条件：

   • $j$ 的范围是 $1$ 到 $n-2$。
   • 因为 $i$ 至少为 0，$k$ 至多为 $n-1$，所以 $j$ 不能是第一个或最后一个元素。

5. 结果处理：

   • 初始化 ans 为负无穷。
   • 最后返回时判断 ans > 0，否则返回 0。