What is a mountain triplet?

A mountain triplet consists of three indices (i, j, k) where i < j < k, nums[i] < nums[j], and nums[k] < nums[j].

What is the time complexity of the brute force solution?

The brute force solution checks all possible triplets, leading to a time complexity of O(n^3), where n is the length of the array.

How can I optimize the brute force solution?

You can optimize the brute force solution by using two loops to find the smallest elements to the left and right of nums[j], reducing the time complexity to O(n^2).

What should I do if no valid mountain triplet exists?

If no valid mountain triplet exists, you should return -1 as specified in the problem statement.

How does GhostInterview help with the problem-solving process?

GhostInterview provides a structured approach to solving the problem, highlights common mistakes, and suggests optimizations to improve both time and space complexity.

#2908

Easy

auto_awesome数组·driven

LeetCode 题解工作台

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

给你一个下标从 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 <= 50
1 <= nums[i] <= 50

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

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate uses brute force but recognizes its inefficiency.
question_mark
Candidate attempts to optimize the brute force solution.
question_mark
Candidate demonstrates an understanding of reducing complexity by leveraging dynamic programming or binary search.

warning

常见陷阱

外企场景

error
Failing to properly check the triplet conditions may lead to incorrect results.
error
Overlooking the case where no valid triplet exists, resulting in an incorrect return value.
error
Choosing the wrong triplet without considering the minimum sum might lead to incorrect answers.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array is in descending order?
arrow_right_alt
What if the array contains only equal elements?
arrow_right_alt
What if the array contains duplicate elements?

help

常见问题

外企场景

继续练习

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