元素和最小的山形三元组 II

难度: Medium

给你一个下标从 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 的山形三元组。

示例 2：

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

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山形三元组。

提示：

3 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁸

Submission

运行时间: 111 ms

内存: 30.7 MB

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = 0, 1
        ans = float('inf')
        for i in range(1, n-1):
            if nums[left] >= nums[i]:
                left = i
                continue
            if right <= i:
                right = n-1
                minRight = right
                while right > i:
                    if nums[minRight] > nums[right]:
                        minRight = right
                    right -= 1
                right = minRight
            if nums[right] >= nums[i]:
                continue
            ans = min(ans, nums[i]+nums[left]+nums[right])
        return ans if ans != float('inf') else -1

Explain

该题解采用了一种改进的暴力搜索方法，用以寻找元素和最小的山形三元组。算法通过单次遍历，同时维护三个指针 left, i, right 分别代表三元组中的三个元素的位置。left 指针始终指向遍历到当前位置 i 前的最小值，而 right 指针则尝试在位置 i 后找到一个小于 nums[i] 的最小元素。每次循环，首先检查 left 指针是否应该更新（即，如果 nums[i] 更小，则更新 left 为当前 i）。然后检查和更新 right 指针，确保 right 指向 i 右侧的最小值，这需要在每次 i 改变时从新从数组尾部向 i 扫描。如果在 i 处的 nums[left] 和 nums[right] 与 nums[i] 形成山形结构，更新最小和 ans。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = 0, 1
        ans = float('inf')
        for i in range(1, n-1):
            # 更新左侧最小值
            if nums[left] >= nums[i]:
                left = i
                continue
            # 确保 right 总是在 i 的右侧
            if right <= i:
                right = n-1
                minRight = right
                # 从右向左查找最小值
                while right > i:
                    if nums[minRight] > nums[right]:
                        minRight = right
                    right -= 1
                right = minRight
            # 判断当前三元组是否为山形
            if nums[right] >= nums[i]:
                continue
            # 更新最小和
            ans = min(ans, nums[i]+nums[left]+nums[right])
        return ans if ans != float('inf') else -1

Explore

这里的关键是保持左指针left始终指向当前遍历到的元素之前的最小值。当遍历到新的元素nums[i]时，如果该元素比nums[left]小或等，这意味着我们找到了一个更小的元素，因此更新left指针为当前索引i。这样做是为了确保当我们在考虑任何中心点i时，left指针指向的是i左侧的最小值，从而使得三元组形成山形结构的可能性增大。如果简单地选择i之前的最小值而不更新left，可能会错过更新的机会，导致不是最优的三元组。

在这个算法实现中，选择从数组尾部向i扫描主要是因为它简单且在遍历过程中易于维护。使用二分查找或有序结构虽然可以提高查找效率，但这样做通常需要额外的数据结构（如平衡树或堆），这会增加实现的复杂性和空间复杂度。此外，每次迭代i时，nums[i]右侧的数组部分都在变化，这使得维护一个动态更新的有序结构变得更加复杂。从尾部向前扫描是一个时间复杂度为O(n)的操作，虽然不是最优，但在整体上保持了算法的简洁性。

如果数组中存在多个相同的最小值，该方法依然可以正确地返回元素和最小的山形三元组。在这种情况下，left指针会在遇到第一个最小值时停止更新。即使后续存在相同的最小值，left指针的位置已经足够保证它是最小的，并且可以与后续的i和right形成有效的山形三元组。算法的核心在于保证left和right正确地指向了能形成山形三元组的元素，而不受具体数值是否相同的影响。

在算法中，如果right指针始终没有更新，即在i的右侧没有找到比nums[i]小的元素，这意味着不能形成山形结构，因此这种情况下不会更新最小和ans。算法会继续遍历其它的i值，直到找到一个合适的right使得nums[right] < nums[i]。如果整个遍历过程中始终找不到符合条件的三元组，算法将返回初始设置的'inf'值，表示不存在有效的山形三元组。这通常会在最后的返回语句中被处理，如果ans仍为'inf'，则返回-1，表示无解。