Medium

题目描述

给你一个下标从 0 开始的整数数组 nums。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山脉三元组：

  • i < j < k
  • nums[i] < nums[j] 且 nums[k] < nums[j]

请你找到所有山脉三元组的 最小可能和，并返回这个 最小和。如果不存在山脉三元组，请返回 -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] = 1 + 5 + 3 = 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] = 4 + 7 + 2 = 13。可以证明不存在和小于 13 的山脉三元组。

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山脉三元组。

提示：

  • 3 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^8

解题思路

这道题要求找到满足山脉条件的三元组的最小和。关键思路是固定中间的峰值位置 j，然后在其左右两侧分别找到最小值作为 i 和 k 位置的候选。

解题思路：

  1. 预处理前缀和后缀最小值数组：

    • prefix_min[i] 表示 nums[0] 到 nums[i] 中的最小值
    • suffix_min[i] 表示 nums[i] 到 nums[n-1] 中的最小值

  2. 枚举峰值位置：

    • 对于每个可能的峰值位置 j（1 <= j <= n-2），检查是否可以构成山脉三元组
    • 左侧最小值必须小于 nums[j]，右侧最小值也必须小于 nums[j]

  3. 计算最小和：

    • 如果位置 j 可以作为峰值，计算 prefix_min[j-1] + nums[j] + suffix_min[j+1]
    • 维护所有可能和的最小值

这种方法的优势是只需要一次预处理和一次遍历，避免了暴力枚举所有三元组的 O(n³) 复杂度。

时间复杂度：O(n) - 预处理数组和一次遍历 空间复杂度：O(n) - 存储前缀和后缀最小值数组

代码实现

class Solution {
public:
    int minimumSum(vector<int>& nums) {
        int n = nums.size();
        
        // 预处理前缀最小值数组
        vector<int> prefix_min(n);
        prefix_min[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix_min[i] = min(prefix_min[i-1], nums[i]);
        }
        
        // 预处理后缀最小值数组
        vector<int> suffix_min(n);
        suffix_min[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffix_min[i] = min(suffix_min[i+1], nums[i]);
        }
        
        int min_sum = INT_MAX;
        
        // 枚举峰值位置j
        for (int j = 1; j < n-1; j++) {
            int left_min = prefix_min[j-1];
            int right_min = suffix_min[j+1];
            
            // 检查是否能构成山脉三元组
            if (left_min < nums[j] && right_min < nums[j]) {
                min_sum = min(min_sum, left_min + nums[j] + right_min);
            }
        }
        
        return min_sum == INT_MAX ? -1 : min_sum;
    }
};

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 预处理前缀最小值数组
        prefix_min = [0] * n
        prefix_min[0] = nums[0]
        for i in range(1, n):
            prefix_min[i] = min(prefix_min[i-1], nums[i])
        
        # 预处理后缀最小值数组
        suffix_min = [0] * n
        suffix_min[n-1] = nums[n-1]
        for i in range(n-2, -1, -1):
            suffix_min[i] = min(suffix_min[i+1], nums[i])
        
        min_sum = float('inf')
        
        # 枚举峰值位置j
        for j in range(1, n-1):
            left_min = prefix_min[j-1]
            right_min = suffix_min[j+1]
            
            # 检查是否能构成山脉三元组
            if left_min < nums[j] and right_min < nums[j]:
                min_sum = min(min_sum, left_min + nums[j] + right_min)
        
        return -1 if min_sum == float('inf') else min_sum

public class Solution {
    public int MinimumSum(int[] nums) {
        int n = nums.Length;
        
        // 预处理前缀最小值数组
        int[] prefixMin = new int[n];
        prefixMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixMin[i] = Math.Min(prefixMin[i-1], nums[i]);
        }
        
        // 预处理后缀最小值数组
        int[] suffixMin = new int[n];
        suffixMin[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffixMin[i] = Math.Min(suffixMin[i+1], nums[i]);
        }
        
        int minSum = int.MaxValue;
        
        // 枚举峰值位置j
        for (int j = 1; j < n-1; j++) {
            int leftMin = prefixMin[j-1];
            int rightMin = suffixMin[j+1];
            
            // 检查是否能构成山脉三元组
            if (leftMin < nums[j] && rightMin < nums[j]) {
                minSum = Math.Min(minSum, leftMin + nums[j] + rightMin);
            }
        }
        
        return minSum == int.MaxValue ? -1 : minSum;
    }
}

var minimumSum = function(nums) {
    const n = nums.length;
    const leftMin = new Array(n);
    const rightMin = new Array(n);
    
    leftMin[0] = nums[0];
    for (let i = 1; i < n; i++) {
        leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
    }
    
    rightMin[n - 1] = nums[n - 1];
    for (let i = n - 2; i >= 0; i--) {
        rightMin[i] = Math.min(rightMin[i + 1], nums[i]);
    }
    
    let minSum = Infinity;
    
    for (let j = 1; j < n - 1; j++) {
        if (leftMin[j - 1] < nums[j] && rightMin[j + 1] < nums[j]) {
            minSum = Math.min(minSum, leftMin[j - 1] + nums[j] + rightMin[j + 1]);
        }
    }
    
    return minSum === Infinity ? -1 : minSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(n)

相关题目