元素和最小的山形三元组 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

// 思路：使用Java Stream API来计算符合条件的三元组，并且找到最小的元素和。我们将遍历每个中心元素，通过流操作来过滤并找到左右两边的最大值
import java.util.stream.IntStream;

public int minimumMountainTripletSumStream(int[] nums) {
    int n = nums.length;
    return IntStream.range(1, n - 1)
        .map(j -> {
            int leftMax = IntStream.range(0, j)
                .filter(i -> nums[i] < nums[j])
                .map(i -> nums[i])
                .max()
                .orElse(Integer.MIN_VALUE);

            int rightMax = IntStream.range(j + 1, n)
                .filter(k -> nums[k] < nums[j])
                .map(k -> nums[k])
                .max()
                .orElse(Integer.MIN_VALUE);

            return (leftMax != Integer.MIN_VALUE && rightMax != Integer.MIN_VALUE) ? leftMax + nums[j] + rightMax : Integer.MAX_VALUE;
        })
        .min()
        .orElse(-1);
}

该题解采用了一种改进的暴力搜索方法，用以寻找元素和最小的山形三元组。算法通过单次遍历，同时维护三个指针 left, i, right 分别代表三元组中的三个元素的位置。left 指针始终指向遍历到当前位置 i 前的最小值，而 right 指针则尝试在位置 i 后找到一个小于 nums[i] 的最小元素。每次循环，首先检查 left 指针是否应该更新（即，如果 nums[i] 更小，则更新 left 为当前 i）。然后检查和更新 right 指针，确保 right 指向 i 右侧的最小值，这需要在每次 i 改变时从新从数组尾部向 i 扫描。如果在 i 处的 nums[left] 和 nums[right] 与 nums[i] 形成山形结构，更新最小和 ans。

O(n^2)

O(1)