当前位置：首页 > article >正文

LeetCode 2909. 元素和最小的山形三元组 II

article 2025/2/3 12:38:20

**### LeetCode 2909. 元素和最小的山形三元组 II

问题描述

给定一个下标从 0 开始的整数数组 nums，我们需要找到一个“山形三元组”（i, j, k）满足以下条件：

i < j < k
nums[i] < nums[j] 且 nums[k] < nums[j]

并且返回这个三元组的元素和 nums[i] + nums[j] + nums[k]。如果不存在符合条件的三元组，返回 -1。

思路分析

我们可以使用优化的双指针方法来高效解决该问题。

关键思路：

前缀和： 遍历数组时，记录每个元素之前的最小值。我们称之为“前缀最小值”。通过前缀最小值可以很快找到左边比当前元素小的元素 nums[i]。
后缀最小值： 类似地，我们还需要维护一个“后缀最小值”数组，记录每个元素后面的最小值。通过后缀最小值，可以快速找到右边比当前元素小的元素 nums[k]。
遍历中间元素： 在固定中间位置 j 的时候，检查其左边是否有比它小的元素 nums[i]（通过前缀最小值）以及右边是否有比它小的元素 nums[k]（通过后缀最小值）。如果存在这样的 i 和 k，就计算当前的三元组和，并更新最小值。
返回结果： 在所有符合条件的三元组中，返回最小和。如果没有符合条件的三元组，返回 -1。

代码实现

class Solution:
    def minimumSum(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] = min(suf[i+1], nums[i])
        
        # 初始化前缀最小值和结果
        pre, ans = nums[0], float('inf')
        
        # 遍历数组，寻找符合条件的三元组
        for i in range(1, n-1):
            if pre < nums[i] > suf[i]:
                ans = min(ans, pre + nums[i] + suf[i+1])
            pre = min(pre, nums[i])
        
        return ans if ans < float('inf') else -1

代码解释

后缀最小值 suf 数组：
```
suf = [0] * n
suf[-1] = nums[-1]
for i in range(n-2, -1, -1):
    suf[i] = min(suf[i+1], nums[i])
```
- 该数组记录每个位置 i 右侧的最小值。suf[i] 表示从位置 i 到数组末尾之间的最小值。
- suf[-1] 初始化为 nums[-1]，然后从后向前计算其他元素的后缀最小值。
前缀最小值 pre 和结果 ans：
```
pre, ans = nums[0], float('inf')
```
- pre 记录当前元素左侧的最小值，用来和当前元素 nums[i] 比较，确保 nums[i] 是一个合法的山形三元组的中间元素。
- ans 用来记录所有符合条件的三元组中的最小和。
遍历并计算三元组和：
```
for i in range(1, n-1):
    if pre < nums[i] > suf[i]:
        ans = min(ans, pre + nums[i] + suf[i+1])
    pre = min(pre, nums[i])
```
- 对每个位置 i，如果 nums[i] 大于 pre（左侧最小值）且大于 suf[i]（右侧最小值），则说明该位置可以作为山形三元组的中间元素 nums[j]。
- 更新最小和 ans，并且在每次遍历时更新 pre，即记录当前元素 nums[i] 作为新的左侧最小值。
返回结果：
```
return ans if ans < float('inf') else -1
```
- 如果 ans 仍然为 float('inf')，则表示没有找到符合条件的三元组，返回 -1。