题目
2908. 元素和最小的山形三元组 I
分析
首先,看到这道题,第一反应就是暴力方法,三层for循环,枚举每一种情况,代码如下
class Solution {
public int minimumSum(int[] nums) {
i服务器托管nt min = Integer.MAX_VALUE;
for(int i = 0;i nums.length - 2;i ++) {
for(int j = i+1;j nums.length - 1;j ++) {
for(int k = j+1;k nums.length;k ++) {
if(nums[i] nums[j] && nums[k] nums[j])
min = Math.min(min,nums[i]+nums[j]+nums[k]);
}
}
}
return min == Integer.MAX_VALUE?-1:min;
}
}
这虽然能通过LeetCode,但是太暴力了。我们还是要想一些其他方法来解决。我们可以利用前后缀
的思想来服务器托管解决,具体思路如下:
枚举nums[i]
,我们需要知道i
左边的最小元素和i
右边的最小元素,得到每一个nums[i]
的左右两个元素和当前nums[i]
相加,最小的值就是我们要求的值。
我们定义 suf[i]
表示 i
右边最小的值(包含i
位置)。我们怎么求的这个值呢????我们从后向前遍历,suf[i] = Math.min(suf[i+1] , nums[i])
前缀最小值pre
采取同样的方法,可以和答案一起计算,所以,只需要定义成一个变量即可。
三个数之和就是:pre + nums[i] + suf[i+1]
。题目也就是让我们求这个的最小值。
代码
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;
}
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
字典树是一种能够快速插入和查询字符串的多叉树结构,节点的编号各不相同,根节点编号为0 Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。 核心思想也是通过空间来换取时间上的效率 在一定情况下字典树的效率要比哈希表要高 字典树在解决…