【灵神题单·贪心】3010. 将数组分成最小总代价的子数组 I | Java

🔗 题目链接：3010. 将数组分成最小总代价的子数组 I
📚 所属题单：灵茶山艾府 · 贪心算法题单 — §1.1 从最小/最大开始贪心
🏷️ 难度：Easy | 难度分：1292
🔖 标签：贪心、数组

📖 题目描述

把长度为 n 的整数数组nums分成3 个连续子数组。每个子数组的代价 = 第一个元素，返回最小代价总和。

示例 1

输入：nums = [1,2,3,12] 输出：6 解释：[1], [2], [3,12]，代价 1+2+3=6

示例 2

输入：nums = [10,3,1,1] 输出：12 解释：[10,3], [1], [1]，代价 10+1+1=12

💡 思路分析

第一个子数组一定从nums[0]开始，代价固定为nums[0]。

另外两个子数组各自的代价是它们的第一个元素——而这两个"分割点"可以是nums[1:]中的任意两个位置。所以问题等价于：在 nums[1:] 中找最小的两个数。

一次遍历，维护最小和次小值就够了 🎯

✅ 代码实现（Java）

classSolution{publicintminimumCost(int[]nums){intfirst=Integer.MAX_VALUE,second=Integer.MAX_VALUE;for(inti=1;i<nums.length;i++){if(nums[i]<first){second=first;first=nums[i];}elseif(nums[i]<second){second=nums[i];}}returnnums[0]+first+second;}}

📊 复杂度分析

🔗 参考

• 灵茶山艾府 · 贪心算法题单

🎯 这题的关键洞察：分割点的代价就是那个位置的元素值，所以最优解就是找 nums[1:] 中最小的两个数。O(n) 一遍搞定，击败 99.91%！