3010.将数组分成最小总代价的子数组 I：排序 OR 维护最小次小

【LetMeFly】3010.将数组分成最小总代价的子数组 I：排序 OR 维护最小次小

力扣题目链接：https://leetcode.cn/problems/divide-an-array-into-subarrays-with-minimum-cost-i/

给你一个长度为 n 的整数数组 nums 。

一个数组的 代价 是它的 第一个 元素。比方说，[1,2,3] 的代价是 1 ，[3,4,1] 的代价是 3 。

你需要将 nums 分成 3 个 连续且没有交集 的子数组。

请你返回这些子数组的 最小 代价 总和 。

 

示例 1：

输入：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 。

示例 2：

输入：nums = [5,4,3]
输出：12
解释：最佳分割成 3 个子数组的方案是：[5] ，[4] 和 [3] ，总代价为 5 + 4 + 3 = 12 。
12 是所有分割方案里的最小总代价。

示例 3：

输入：nums = [10,3,1,1]
输出：12
解释：最佳分割成 3 个子数组的方案是：[10,3] ，[1] 和 [1] ，总代价为 10 + 1 + 1 = 12 。
12 是所有分割方案里的最小总代价。

 

提示：

• 3 <= n <= 50
• 1 <= nums[i] <= 50

解题方法：排序 OR 维护最小次小

不难发现，$nums[0]$必被第一个子数组选中，后续数组中可以分别将最小值和次小值作为后面两个数组的起始元素。

排序法

对$nums$除第一个元素外的其他部分排序，返回数组前三个元素就好了。

维护最小次小

两个变量$min1$和$min2$分别维护除第一个元素外其他部分的最小值和次小值，遍历过程中：

• 若元素小于等于最小值则令次小值等于最小值，最小值等于该元素
• 否则，若元素小于次小值，则令次小值等于该元素

时空复杂度分析

• 时间复杂度：排序$O(n\log n)$、最小次小$O(n)$
• 空间复杂度：排序$O(\log n)$、最小次小$O(1)$

AC代码

C++ - 排序

/*
 * @LastEditTime: 2026-02-01 09:51:34
 */
class Solution {
public:
    int minimumCost(vector<int>& nums) {
        sort(nums.begin() + 1, nums.end());
        return nums[0] + nums[1] + nums[2];
    }
};

C++ - 最小次小

/*
 * @LastEditTime: 2026-02-01 09:56:48
 */
class Solution {
public:
    int minimumCost(vector<int>& nums) {
        int min1 = 100, min2 = 100;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] <= min1) {
                min2 = min1;
                min1 = nums[i];
            } else if (nums[i] < min2) {
                min2 = nums[i];
            }
        }
        return nums[0] + min1 + min2;
    }
};

Python - 排序一行版

'''
LastEditTime: 2026-02-01 10:06:51
'''
from typing import List

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        return nums[0] + sum(sorted(nums[1:])[:2])

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源