Leetcode 2909. Minimum Sum of Mountain Triplets II

本文主要是介绍Leetcode 2909. Minimum Sum of Mountain Triplets II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• Leetcode 2909. Minimum Sum of Mountain Triplets II
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：2909. Minimum Sum of Mountain Triplets II

1. 解题思路

这一题思路上就是一个累积数组的思路。

我们要找一个山峰结构，使得其和最小，那么我们只需要遍历每一个位置作为峰值时其能够构成的最小山峰的和。

而对于一个确定的峰的位置，要求得其最小山峰的和，就是分别在其左右两侧取最小元素，然后判断其是否均小于这个值本身即可。

2. 代码实现

给出python代码实现如下：

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

提交代码评测得到：耗时959ms，占用内存31.8MB。

这篇关于Leetcode 2909. Minimum Sum of Mountain Triplets II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---