What is the minimum sum of mountain triplets?

The minimum sum is the sum of the smallest values on the left and right of the middle element of the triplet. This ensures that the conditions of a mountain triplet are met.

How can I efficiently find the left and right values for each index?

You can use pre-computed arrays to store the smallest value up to each index and the largest value from each index onward, allowing for constant-time lookup during the iteration.

How do I handle the case where no mountain triplet exists?

If no valid triplet can be formed, return -1 as per the problem's requirements. This is typically checked after the main traversal.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the array. This is achieved by using pre-computed arrays to quickly find the left and right values for each middle index.

How can I apply this problem-solving approach to other similar problems?

This array-driven strategy of pre-computing values for efficient lookups is applicable in many problems involving triplets or other patterns where the left and right values matter, such as in finding local maxima or minima.

#2909

Medium

auto_awesome数组·driven

LeetCode 题解工作台

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

给你一个下标从 0 开始的整数数组 nums 。如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个山形三元组： i nums[i] 且 nums[k] 请你找出 nums 中元素和最小的山形三元组，并返回其元素和。如果不存在满足条件的三元组，返回 -1 。示例 1：…

数组

题目描述

给你一个下标从 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⁸

lightbulb

解题思路

方法一：预处理 + 枚举

我们可以预处理出每个位置右侧的最小值，记录在数组 $right[i]$ 中，即 $right[i]$ 表示 $nums[i+1..n-1]$ 中的最小值。

接下来，我们从左到右枚举山形三元组的中间元素 $nums[i]$ ，用一个变量 $left$ 表示 $nums[0..i-1]$ 中的最小值，用一个变量 $ans$ 表示当前找到的最小元素和。对于每个 $i$ ，我们需要找到满足 $left < nums[i]$ 且 $right[i+1] < nums[i]$ 的元素 $nums[i]$ ，并更新 $ans$ 。

最后，如果 $ans$ 仍然为初始值，则说明不存在山形三元组，返回 $-1$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        right = [inf] * (n + 1)
        for i in range(n - 1, -1, -1):
            right[i] = min(right[i + 1], nums[i])
        ans = left = inf
        for i, x in enumerate(nums):
            if left < x and right[i + 1] < x:
                ans = min(ans, left + x + right[i + 1])
            left = min(left, x)
        return -1 if ans == inf else ans

speed

复杂度分析

指标	值
时间	complexity depends on the approach used for computing left and right minimum/maximum values. If pre-computed arrays are used, the time complexity is O(n). Space complexity will also be O(n) for storing these arrays.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a solution that optimizes the left and right value search for each middle index.
question_mark
Focus on the efficiency of the pre-computation of left and right values.
question_mark
Evaluate how well the candidate handles edge cases where no valid triplet exists.

warning

常见陷阱

外企场景

error
Not using efficient array traversal techniques can lead to a solution that does not meet time limits for larger arrays.
error
Failing to correctly handle the edge case where no valid mountain triplet exists.
error
Choosing the wrong approach to find the left and right values, leading to higher time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Generalize the solution to handle arrays with varying sizes and edge cases.
arrow_right_alt
Optimize the approach for arrays with large values (up to 10^8) and large lengths (up to 10^5).
arrow_right_alt
Extend the problem to find multiple mountain triplets and return the one with the smallest sum.

help

常见问题

外企场景

继续练习

#2908 元素和最小的山形三元组 I #2910 合法分组的最少组数 #2906 构造乘积矩阵