[LeetCode] 2909. Minimum Sum of Mountain Triplets II

You are given a 0-indexed array nums of integers.

A triplet of indices (i, j, k) is a mountain if:
i < j < k
nums[i] < nums[j] and nums[k] < nums[j]
Return the minimum possible sum of a mountain triplet of nums. If no such triplet exists, return -1.

Example 1:
Input: nums = [8,6,1,5,3]
Output: 9
Explanation: Triplet (2, 3, 4) is a mountain triplet of sum 9 since:

• 2 < 3 < 4
• nums[2] < nums[3] and nums[4] < nums[3]
  And the sum of this triplet is nums[2] + nums[3] + nums[4] = 9. It can be shown that there are no mountain triplets with a sum of less than 9.

Example 2:
Input: nums = [5,4,8,7,10,2]
Output: 13
Explanation: Triplet (1, 3, 5) is a mountain triplet of sum 13 since:

• 1 < 3 < 5
• nums[1] < nums[3] and nums[5] < nums[3]
  And the sum of this triplet is nums[1] + nums[3] + nums[5] = 13. It can be shown that there are no mountain triplets with a sum of less than 13.

Example 3:
Input: nums = [6,5,4,3,4,5]
Output: -1
Explanation: It can be shown that there are no mountain triplets in nums.

Constraints:
3 <= nums.length <= 105
1 <= nums[i] <= 108

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

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

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

• i < j < k
• nums[i] < nums[j] 且 nums[k] < nums[j]
  请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

思路

我参考了这个帖子。这是一道类似 two sum 的题。题目要求我们找到一个三元组满足如下条件

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

那么我们可以枚举 j，需要遍历两遍数组。
第一次遍历 input 数组，先用两个数组分别记录 j 左侧最小的 i 和 j 右侧最大的 k，记为premin和suffmin。
第二次遍历 input 数组，对于每个下标 j，我们看一看他左侧的最小值，右侧的最小值和他自己是否满足nums[i] < nums[j] 且 nums[k] < nums[j]这个式子。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;
        int[] premin = new int[n];
        int min = nums[0];
        for (int i = 1; i < n; i++) {
            premin[i] = min;
            min = Math.min(min, nums[i]);
        }

        int[] suffmin = new int[n];
        min = nums[n - 1];
        for (int i = n - 1; i >= 1; i--) {
            suffmin[i] = min;
            min = Math.min(min, nums[i]);
        }

        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n - 1; i++) {
            int cur = nums[i];
            if (premin[i] < cur && suffmin[i] < cur) {
                res = Math.min(res, premin[i] + cur + suffmin[i]);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}