哪里建设企业网站,关于卖零食网站建设需求分析,废旧材料手工制作大全,做单页网站Every day a Leetcode
题目来源#xff1a;2909. 元素和最小的山形三元组 II
解法1#xff1a;枚举 前后缀分解
定义 preMin[i] 为前缀最小值#xff0c;初始化 preMin[0] nums[0]#xff0c;递推公式#xff1a;preMin[i] min(preMin[i - 1], nums[i])。
定义 suf…Every day a Leetcode
题目来源2909. 元素和最小的山形三元组 II
解法1枚举 前后缀分解
定义 preMin[i] 为前缀最小值初始化 preMin[0] nums[0]递推公式preMin[i] min(preMin[i - 1], nums[i])。
定义 sufMin[i] 为后缀最小值初始化 sufMin[n - 1] nums[n - 1]递推公式sufMin[i] min(sufMin[i 1], nums[i])。
枚举 nums[j]答案为 preMin[j - 1] nums[j] sufMin[j 1] 的最小值。
代码
/** lc appleetcode.cn id2909 langcpp** [2909] 元素和最小的山形三元组 II*/// lc codestart
class Solution
{
public:int minimumSum(vectorint nums){int n nums.size();vectorint preMin(n);preMin[0] nums[0];for (int i 1; i n; i)preMin[i] min(preMin[i - 1], nums[i]);vectorint sufMin(n);sufMin[n - 1] nums[n - 1];for (int i n - 2; i 0; i--)sufMin[i] min(sufMin[i 1], nums[i]);int minimumSum INT_MAX;for (int j 1; j n - 1; j)if (preMin[j - 1] nums[j] nums[j] sufMin[j 1])minimumSum min(minimumSum, preMin[j - 1] nums[j] sufMin[j 1]);return minimumSum INT_MAX ? -1 : minimumSum;}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 是数组 nums 的长度。
空间复杂度O(n)其中 n 是数组 nums 的长度。
