LeetCode 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 维护最小次小

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

排序法

对n u m s numsnums除第一个元素外的其他部分排序，返回数组前三个元素就好了。

维护最小次小

两个变量m i n 1 min1min1和m i n 2 min2min2分别维护除第一个元素外其他部分的最小值和次小值，遍历过程中：

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

时空复杂度分析

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

AC代码

C++ - 排序

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

C++ - 最小次小

/* * @LastEditTime: 2026-02-01 09:56:48 */classSolution{public:intminimumCost(vector<int>&nums){intmin1=100,min2=100;for(inti=1;i<nums.size();i++){if(nums[i]<=min1){min2=min1;min1=nums[i];}elseif(nums[i]<min2){min2=nums[i];}}returnnums[0]+min1+min2;}};

Python - 排序一行版

''' LastEditTime: 2026-02-01 10:06:51 '''fromtypingimportListclassSolution:defminimumCost(self,nums:List[int])->int:returnnums[0]+sum(sorted(nums[1:])[:2])

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

千篇源码题解已开源