山形三元组

山形三元组"/>

山形三元组

可以先考虑两个数的情况，即找到一个数作为中间点，左边找到最小值，右边找到最小值，计算三个数的和。然后枚举中间点，计算所有可能的和中的最小值即可。

代码如下：

class Solution:def minTotal(self, nums: List[int]) -> int:n = len(nums)res = float('inf')for j in range(1, n - 1):left_min, right_min = float('inf'), float('inf')for i in range(j):if nums[i] < nums[j]:left_min = min(left_min, nums[i])for k in range(j + 1, n):if nums[k] < nums[j]:right_min = min(right_min, nums[k])if left_min != float('inf') and right_min != float('inf'):res = min(res, left_min + nums[j] + right_min)return res if res != float('inf') else -1

时间复杂度为O(n^3)，可以通过本题，但不是最优解。