题目描述
给你一个长度为 n
的整数数组 nums
。
一个数组的 代价 是它的 第一个 元素。比方说,[1,2,3]
的代价是 1
,[3,4,1]
的代价是 3
。
你需要将 nums
分成 3
个 连续且没有交集 的子数组。
请你返回这些子数组的 最小 代价 总和。
样例
输入:nums = [1,2,3,12]
输出:6
解释:最佳分割成 3 个子数组的方案是:[1],[2] 和 [3,12],总代价为 1 + 2 + 3 = 6。
其他得到 3 个子数组的方案是:
- [1],[2,3] 和 [12],总代价是 1 + 2 + 12 = 15。
- [1,2],[3] 和 [12],总代价是 1 + 3 + 12 = 16。
输入:nums = [5,4,3]
输出:12
解释:最佳分割成 3 个子数组的方案是:[5],[4] 和 [3],总代价为 5 + 4 + 3 = 12。
12 是所有分割方案里的最小总代价。
输入:nums = [10,3,1,1]
输出:12
解释:最佳分割成 3 个子数组的方案是:[10,3],[1] 和 [1],总代价为 10 + 1 + 1 = 12。
12 是所有分割方案里的最小总代价。
限制
3 <= n <= 50
1 <= nums[i] <= 50
算法
(思维题) $O(n)$
- 第一个子数组的代价必定是 $nums(0)$,剩下两个子数组的代价相当于除去第一个元素之外,剩余元素中的最小值和次小值。
时间复杂度
- 遍历数组一次,时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minimumCost(vector<int>& nums) {
const int n = nums.size();
int mi1 = INT_MAX, mi2 = INT_MAX;
for (int i = 1; i < n; i++) {
if (nums[i] < mi1) {
mi2 = mi1;
mi1 = nums[i];
} else if (nums[i] < mi2) {
mi2 = nums[i];
}
}
return nums[0] + mi1 + mi2;
}
};