目标
给你一个下标从 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
思路
它标的是一道简单题，但是在我思考的过程中甚至产生了自我怀疑。以至于后面有些抓狂，直接暴力求解，不考虑性能，不考虑优雅，什么都不顾，只要能做出来。好以此来证明自己不是那么傻。
这道题让我们求数组中满足某些条件的三元组之中和最小的那一个，满足的条件就是 小 大 小，可以不连续。
暴力解法上来直接就排除了，什么动态规划直接pass。简单题需要这些吗？然后我就被上了一课，不用这些真想不出来。方法没有高低之分。
代码
/**
* @date 2024-03-29 0:52
*/
public class MinimumSum2908 {
public int minimumSum(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = Integer.MAX_VALUE;
dp[nums.length - 1] = Integer.MAX_VALUE;
for (int i = 1; i < nums.length; i++) {
int tmp = i;
int left = Integer.MAX_VALUE;
while (i >= 1) {
if (nums[tmp] > nums[i - 1]) {
left = Math.min(left, nums[i - 1]);
}
i--;
}
if (left == Integer.MAX_VALUE) {
dp[tmp] = Integer.MAX_VALUE;
i = tmp;
continue;
}
int right = Integer.MAX_VALUE;
i = tmp;
while (i < nums.length - 1) {
if (nums[tmp] > nums[i + 1]) {
right = Math.min(right, nums[i + 1]);
}
i++;
}
if (right != Integer.MAX_VALUE) {
dp[tmp] = left + nums[tmp] + right;
} else {
dp[tmp] = Integer.MAX_VALUE;
}
i = tmp;
}
Arrays.sort(dp);
return dp[0] == Integer.MAX_VALUE ? -1 : dp[0];
}
}
性能
