各电商网站的特点,网页视频下载工具哪个好,建站网站都用不了的,手机购物网站模板**### LeetCode 2909. 元素和最小的山形三元组 II
问题描述
给定一个下标从 0 开始的整数数组 nums#xff0c;我们需要找到一个“山形三元组”#xff08;i, j, k#xff09;满足以下条件#xff1a;
i j knums[i] nums[j] 且 nums[k] nums[j]
并…**### LeetCode 2909. 元素和最小的山形三元组 II
问题描述
给定一个下标从 0 开始的整数数组 nums我们需要找到一个“山形三元组”i, j, k满足以下条件
i j knums[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] * nsuf[-1] nums[-1]for i in range(n-2, -1, -1):suf[i] min(suf[i1], 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[i1])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[i1], 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[i1])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。 时间复杂度
计算后缀最小值的时间复杂度是 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) 的时间复杂度能够处理大规模数据输入。**
