【力扣每日一题】2908. 元素和最小的山形三元组 I

LC2908. 元素和最小的山形三元组 I

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

i < j < k
nums[i] < nums[j] 且 nums[k] < nums[j]
请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

示例 1：
输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为： 2 < 3 < 4
nums[2] < nums[3] 且 nums[4] < nums[3]
这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。

提示：

3 <= nums.length <= 50
1 <= nums[i] <= 50

纯暴力代码

三重循环，时间复杂度O（n^3）

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

枚举j的思路

也可以枚举j，然后，在内存分别枚举i和k，这样时间复杂度是O（n^2）

AC代码

预处理前后缀O（n）
我们发现，如果枚举j的前提下，我还需要用O（n）找到前缀/后缀的最小值，其实这一步可以用预处理的方式在循环外部先计算出来，最后再以O（1）去调用即可

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        ans = inf
        l = [inf]*n
        r = [inf]*n
        mi = inf
        for i in range(n):
            mi = min(mi,nums[i])
            l[i] = mi
        mi = inf
        for i in range(n-1,-1,-1):
            mi = min(mi,nums[i])
            r[i] = mi

        for i in range(1,n-1):
            lmi = l[i-1]
            rmi = r[i+1]
            if lmi<nums[i] and nums[i]>rmi:
                ans = min(ans,lmi+rmi+nums[i])
        return ans if ans!=inf else -1