Tag

【预处理+枚举】【数组】【2024-03-29】

---

题目来源

2908. 元素和最小的山形三元组 I

---

解题思路

方法一：预处理+枚举

思路

朴素的方法是枚举所有可能的 山形三元组，找出最小的元素和。该方法的时间复杂度为 $O(n^3)$，对于本题的数据规模完全可以通过。

但是有最优的解法，对数组进行预处理，维护两个数组 leftMin 和 rightMin ，leftMin[i] 表示位置 i 处及其左侧最小的元素值，rightMin[i] 表示位置 i 处及其右侧最小的元素值。

最后枚举 山形三元组 的中间位置元素，找出符合要求的最小元素和。

具体实现见代码。

实现代码

class Solution {
public:int minimumSum(vector<int>& nums) {int n = nums.size();vector<int> leftMin(n), rightMin(n);leftMin[0] = nums[0];for (int i = 1; i < n; ++i) {leftMin[i] = min(leftMin[i-1], nums[i]);}rightMin[n-1] = nums[n-1];for (int i = n-2; i >= 0; --i) {rightMin[i] = min(rightMin[i+1], nums[i]);}int res = 300;for (int i = 1; i < n-1; ++i) {if (nums[i] > leftMin[i-1] && nums[i] > rightMin[i+1])res = min(res, nums[i] + leftMin[i-1] + rightMin[i+1]);}return res == 300 ? -1 : res;}
};

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组 nums 的长度。

空间复杂度：$O(n)$。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。