学完js了可以做哪些网站,深圳龙岗区住房和建设局网站官网,公司网站流程,wordpress粒子插件LeetCode
元素和最小的山形三元组 I
题目链接#xff1a;
题目描述
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件#xff0c;则认为它是一个 山形三元组 #xff1a;
i j knums[i] nums[j] 且 nums[k] nu…LeetCode
元素和最小的山形三元组 I
题目链接
题目描述
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件则认为它是一个 山形三元组
i j knums[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 501 nums[i] 50
思路
前后缀分解 大佬题解 2908. 元素和最小的山形三元组 I - 力扣LeetCode 代码
C
class Solution {
public:int minimumSum(vectorint nums) {int n nums.size();vectorint suf(n);suf[n - 1] nums[n - 1];for(int i n - 2; i 1; i--){suf[i] min(suf[i 1],nums[i]);}int ans INT_MAX;int pre nums[0];for(int i 1; i n - 1;i){if(pre nums[i] nums[i] suf[i 1]){ans min(ans, pre nums[i] suf[i 1]);}pre min(nums[i],pre);}return ans INT_MAX ? -1 : ans;}
};Java
class Solution {public int minimumSum(int[] nums) {int n nums.length;int[] suf new int [n];suf[n - 1] nums[n - 1];for(int i n - 2; i 1; i--){suf[i] Math.min(suf[i 1], nums[i]);}int ans Integer.MAX_VALUE;int pre nums[0];for(int i 1; i n - 1; i){if(pre nums[i] nums[i] suf[i 1]){ans Math.min(ans, pre nums[i] suf[i 1]);}pre Math.min(pre, nums[i]);}return ans Integer.MAX_VALUE ? - 1 : ans;}
}
