黄页哪个网站好_seo网站管理招聘_线上营销渠道主要有哪些_百度怎么打广告

LeetCode 2873: 有序三元组中的最大值问题详解

题目描述

题目给定一个整数数组 nums，要求找出满足条件 i < j < k 的三元组 (i, j, k)，使得 (nums[i] - nums[j]) * nums[k] 的值最大。如果所有可能的三元组值都为负数，则返回 0。

示例:

• 输入: nums = [12,6,1,2,7]

• 输出: 77

• 解释: 三元组 (0,2,4) 的值为 (12-1)*7 = 77

• 输入: nums = [1,10,3,4,19]

• 输出: 133

• 解释: 三元组 (1,2,4) 的值为 (10-3)*19 = 133

• 输入: nums = [1,2,3]

• 输出: 0

• 解释: 唯一的三元组 (0,1,2) 值为 (1-2)*3 = -3，为负数，故返回 0

提示:

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

问题理解与分析

在这个问题中，需要寻找三个位置，使得第一个位置的值减去第二个位置的值，再乘以第三个位置的值最大。有一些值得思考的点：

1. 希望 nums[i] - nums[j] 尽可能大
2. 同时也希望 nums[k] 尽可能大
3. 还需要考虑正负号的影响

一起探讨几种不同的解题思路，从简单到复杂，逐步优化。

解法一：朴素的三重循环

最直接的方法可能是尝试所有可能的三元组组合：

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

这种方法简单明了，容易理解，但时间复杂度为 O(n³)，对于较大规模的输入可能不太理想。

解法二：线性时间的优化方法

观察公式 (nums[i] - nums[j]) * nums[k]，可以想到一种更高效的方法。对于每个位置 k，只需要知道在它之前的最大 nums[i] - nums[j] 值即可：

class Solution:def maximumTripletValue(self, nums: List[int]) -> int:n = len(nums)max_value = 0max_diff = 0  # 记录最大的 nums[i] - nums[j]max_i = 0     # 记录之前遇到的最大值for k in range(n):# 更新结果if k >= 2:max_value = max(max_value, max_diff * nums[k])# 更新最大差值if k >= 1:max_diff = max(max_diff, max_i - nums[k])# 更新最大元素max_i = max(max_i, nums[k])return max_value

这种方法通过一次遍历就能得到结果，时间复杂度降低到了 O(n)，是一种相当高效的解法。

解法三：前缀最大值与后缀最大值

另一种思路是利用前缀和后缀信息：

class Solution:def maximumTripletValue(self, nums: List[int]) -> int:n = len(nums)max_value = 0# 计算前缀最大值prefix_max = [0] * nprefix_max[0] = nums[0]for i in range(1, n):prefix_max[i] = max(prefix_max[i-1], nums[i])# 计算后缀最大值suffix_max = [0] * nsuffix_max[n-1] = nums[n-1]for i in range(n-2, -1, -1):suffix_max[i] = max(suffix_max[i+1], nums[i])# 枚举中间位置jfor j in range(1, n-1):# 只考虑能产生正差值的情况if prefix_max[j-1] > nums[j]:max_value = max(max_value, (prefix_max[j-1] - nums[j]) * suffix_max[j+1])return max_value

这种方法的思路比较清晰，虽然需要额外 O(n) 的空间，但也只需要 O(n) 的时间复杂度。

解法四：优化的两重循环

还可以考虑一种介于暴力解法和最优解法之间的方法：

class Solution:def maximumTripletValue(self, nums: List[int]) -> int:n = len(nums)max_value = 0for k in range(2, n):# 对于当前k，找出之前所有可能的i,j组合中的最大差值max_diff = 0for j in range(k):for i in range(j):max_diff = max(max_diff, nums[i] - nums[j])# 计算当前k位置的最大三元组值max_value = max(max_value, max_diff * nums[k])return max_value

这种方法比完全的暴力搜索要高效一些，但时间复杂度仍为 O(n^3)，不是最优选择。

算法复杂度分析

比较一下各种解法的时间和空间复杂度：

解法	时间复杂度	空间复杂度	特点
朴素三重循环	O(n³)	O(1)	简单直观，适合理解问题
线性时间优化	O(n)	O(1)	效率最高，需要一些思考
前缀后缀数组	O(n)	O(n)	思路清晰，需要额外空间
优化两重循环	O(n³)	O(1)	介于暴力和最优之间

解题心得与总结

经过对这个问题的深入思考，线性时间的解法可能是最佳选择，它既保持了较低的时间复杂度，又不需要额外的空间。

这道题目给我的启示是，有时候看似需要枚举所有组合的问题，通过巧妙的观察和思考，常常能找到更高效的解法。在面对类似问题时，可以尝试：

1. 先理解问题本质，确定需要计算的目标
2. 考虑是否可以利用前缀/后缀信息
3. 尝试将多重循环优化为单次遍历
4. 善用变量记录中间状态，避免重复计算