文章目录
- Tag
- 题目来源
- 解题思路
- 方法一:预处理+枚举
- 写在最后
Tag
【预处理+枚举】【数组】【2024-03-29】
题目来源
2908. 元素和最小的山形三元组 I
解题思路
方法一:预处理+枚举
思路
朴素的方法是枚举所有可能的 山形三元组,找出最小的元素和。该方法的时间复杂度为 O ( n 3 ) O(n^3) O(n3),对于本题的数据规模完全可以通过。
但是有最优的解法,对数组进行预处理,维护两个数组 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 ) O(n) O(n), n n n 为数组 nums
的长度。
空间复杂度: O ( n ) O(n) O(n)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。