leetcode-2874

题目

https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-ii/description/?envType=daily-question&envId=2025-04-03

分析

• 题目逻辑同 2873一样，两道题的差别在于数据量。
• 因为是查询一个三元组，如果暴力查询O(n³)，2874无法通过
• 由题意可知
  • (i,j,k) ans = max(nums[i] - nums[j]) * nums[k])
  • i < j < k, 所有nums大于0
  • i,k要大，j要小
• 所以可以通过辅助数据记录i,k
• 遍历j,选每个j两侧的最大i,k
  • 两个最大值辅助数组记录nums[i],nums[k]
  • 时间O(2n) 空间O(2n)
• 进一步优化，遍历j的时候记录i或k,省一个辅助数组
  • 时间O(2n) 空间O(n)
• 更进一步优化 双指针
  • 时间O(n) 空间O(1)
  • 遍历k 记录最大的(nums[i] - nums[j])

源代码

https://github.com/Norton-Lin/algorithm/blob/master/go/src/leetcode_2873/2025_04_02_2873.go
https://github.com/Norton-Lin/algorithm/blob/master/go/src/leetcode_2874/2025_04_03_2874.go