题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个数组，找到其中值最大的三元组，三元组要求下标 i < j < k，值计算公式为(nums[i]-nums[j])*nums[k]。

思路分享

  • 基本的枚举思路可以参考【Leetcode Daily】2909元素和最小的山形三元组。

  • 从值的计算可以轻松得知，要是得值尽可能的大，nums[i] 和 nums[k] 都要尽可能大，而 nums[j] 要尽可能小。

  • 于是就可以预处理数组，找到每个位置上下标往右的最大值，这样在遍历过程中就能以 O(1) 的复杂度获取到能用的最大的 nums[k] 值。接着在遍历过程中顺便记录最大值当作 nums[i] 用即可。

  • 类似思路更完整的解析已在历史题说过，故上面只是简单叙述思路。历史题目：【Leetcode Daily】2909元素和最小的山形三元组。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        # 可以看到，前面要求尽可能大，后面也尽可能大，或许能先处理后缀
        n = len(nums)
        suf = [0] * n
        suf[-1] = nums[-1]
        for i in range(n-2, 1, -1):
            suf[i] = max(suf[i+1], nums[i])
            
        # print(suf)

        max_pre_num = nums[0]
        ans = 0
        for i in range(1, n-1):
            # print(f"({max_pre_num}-{nums[i]})*{suf[i+1]}")
            ans = max((max_pre_num-nums[i])*suf[i+1], ans)
            max_pre_num = max(max_pre_num, nums[i])

        return ans