网站建设 中关村,莱芜网络营销代理,vps空间如何做网站备份,重庆市建设岗培中心网站目录 一、题目
1、题目描述
2、接口描述
cpp
python3
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
cpp
python3 一、题目
1、题目描述 给你一个下标从 0 开始的整数数组 nums 。 如果下标三元组 (i, j, k) 满足下述全部条件#xff0c;则认为…目录 一、题目
1、题目描述
2、接口描述
cpp
python3
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
cpp
python3 一、题目
1、题目描述 给你一个下标从 0 开始的整数数组 nums 。 如果下标三元组 (i, j, k) 满足下述全部条件则认为它是一个 山形三元组 i j knums[i] nums[j] 且 nums[k] nums[j] 请你找出 nums 中 元素和最小 的山形三元组并返回其 元素和 。如果不存在满足条件的三元组返回 -1 。 2、接口描述
cpp
class Solution {
public:int minimumSum(vectorint nums) {}
};
python3
class Solution:def minimumSum(self, nums: List[int]) - int:
3、原题链接
2908. 元素和最小的山形三元组 I 二、解题报告
1、思路分析
预处理pre[i]pre[i]即[0, i - 1]中最小的数
同理后缀最小也可以预处理不过我们可以倒序遍历的时候维护
如果nums[i] pre[i] nums[i] post[i]那么就维护答案
2、复杂度 时间复杂度 O(n)空间复杂度O(n) 3、代码详解
cpp
class Solution {
public:int minimumSum(vectorint nums) {int n nums.size(), ret 180;vectorint pre;for(int i 0, mi 55; i n; i)pre.emplace_back(mi), mi min(mi, nums[i]);for(int i n - 2, mi nums[n - 1]; i 0; i--){if(nums[i] pre[i] nums[i] mi)ret min(ret, pre[i] nums[i] mi);mi min(mi, nums[i]);}return ret ! 180 ? ret : -1;}
};
python3
class Solution:def minimumSum(self, a: List[int]) - int:pre []n, mi, ret len(a), 55, 180for x in a:pre.append(mi)mi min(mi, x)mi a[n - 1]for i in range(n - 2, 0, -1):if pre[i] a[i] mi:ret min(ret, a[i] pre[i] mi)mi min(mi, a[i])return ret if ret 180 else -1
