山形三元组"/>
山形三元组
可以先考虑两个数的情况,即找到一个数作为中间点,左边找到最小值,右边找到最小值,计算三个数的和。然后枚举中间点,计算所有可能的和中的最小值即可。
代码如下:
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),可以通过本题,但不是最优解。
更多推荐
山形三元组
发布评论