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

**### 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。

---

思路分析

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

关键思路：

1. 前缀和： 遍历数组时，记录每个元素之前的最小值。我们称之为“前缀最小值”。通过前缀最小值可以很快找到左边比当前元素小的元素 nums[i]。

2. 后缀最小值： 类似地，我们还需要维护一个“后缀最小值”数组，记录每个元素后面的最小值。通过后缀最小值，可以快速找到右边比当前元素小的元素 nums[k]。

3. 遍历中间元素： 在固定中间位置 j 的时候，检查其左边是否有比它小的元素 nums[i]（通过前缀最小值）以及右边是否有比它小的元素 nums[k]（通过后缀最小值）。如果存在这样的 i 和 k，就计算当前的三元组和，并更新最小值。

4. 返回结果： 在所有符合条件的三元组中，返回最小和。如果没有符合条件的三元组，返回 -1。

---

代码实现

class Solution:def minimumSum(self, nums: List[int]) -> int:n = len(nums)# 计算后缀最小值数组suf = [0] * nsuf[-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

代码解释

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]，然后从后向前计算其他元素的后缀最小值。

2. 前缀最小值 pre 和结果 ans：

   pre, ans = nums[0], float('inf')
   

   • pre 记录当前元素左侧的最小值，用来和当前元素 nums[i] 比较，确保 nums[i] 是一个合法的山形三元组的中间元素。
   • ans 用来记录所有符合条件的三元组中的最小和。

3. 遍历并计算三元组和：

   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] 作为新的左侧最小值。

4. 返回结果：

   return ans if ans < float('inf') else -1
   

   • 如果 ans 仍然为 float('inf')，则表示没有找到符合条件的三元组，返回 -1。

---

时间复杂度

• 计算后缀最小值的时间复杂度是 O(n)。
• 遍历数组的时间复杂度是 O(n)。

因此，总的时间复杂度是 O(n)，对于 n 最大为 10^5 的情况非常高效。

---

示例分析

示例 1：

输入：

nums = [8, 6, 1, 5, 3]

输出：

9

解释：三元组 (2, 3, 4) 满足条件，最小和为 nums[2] + nums[3] + nums[4] = 9。

示例 2：

输入：

nums = [5, 4, 8, 7, 10, 2]

输出：

13

解释：三元组 (1, 3, 5) 满足条件，最小和为 nums[1] + nums[3] + nums[5] = 13。

示例 3：

输入：

nums = [6, 5, 4, 3, 4, 5]

输出：

-1

解释：没有符合条件的山形三元组。

---

总结

通过计算前缀和后缀最小值数组，并结合双指针技巧，我们能够高效地找到符合条件的山形三元组并计算其最小和。这样，我们的解决方案达到了 O(n) 的时间复杂度，能够处理大规模数据输入。**