题目链接3010. 将数组分成最小总代价的子数组 I 所属题单灵茶山艾府 · 贪心算法题单 — §1.1 从最小/最大开始贪心️ 难度Easy | 难度分1292 标签贪心、数组 题目描述把长度为 n 的整数数组nums分成3 个连续子数组。每个子数组的代价 第一个元素返回最小代价总和。示例 1输入nums [1,2,3,12] 输出6 解释[1], [2], [3,12]代价 1236示例 2输入nums [10,3,1,1] 输出12 解释[10,3], [1], [1]代价 101112 思路分析第一个子数组一定从nums[0]开始代价固定为nums[0]。另外两个子数组各自的代价是它们的第一个元素——而这两个分割点可以是nums[1:]中的任意两个位置。所以问题等价于在 nums[1:] 中找最小的两个数。一次遍历维护最小和次小值就够了 ✅ 代码实现JavaclassSolution{publicintminimumCost(int[]nums){intfirstInteger.MAX_VALUE,secondInteger.MAX_VALUE;for(inti1;inums.length;i){if(nums[i]first){secondfirst;firstnums[i];}elseif(nums[i]second){secondnums[i];}}returnnums[0]firstsecond;}} 复杂度分析复杂度说明⏱️ 时间O(n)一次遍历 空间O(1)常数空间 参考灵茶山艾府 · 贪心算法题单 这题的关键洞察分割点的代价就是那个位置的元素值所以最优解就是找 nums[1:] 中最小的两个数。O(n) 一遍搞定击败 99.91%
【灵神题单·贪心】3010. 将数组分成最小总代价的子数组 I | Java
题目链接3010. 将数组分成最小总代价的子数组 I 所属题单灵茶山艾府 · 贪心算法题单 — §1.1 从最小/最大开始贪心️ 难度Easy | 难度分1292 标签贪心、数组 题目描述把长度为 n 的整数数组nums分成3 个连续子数组。每个子数组的代价 第一个元素返回最小代价总和。示例 1输入nums [1,2,3,12] 输出6 解释[1], [2], [3,12]代价 1236示例 2输入nums [10,3,1,1] 输出12 解释[10,3], [1], [1]代价 101112 思路分析第一个子数组一定从nums[0]开始代价固定为nums[0]。另外两个子数组各自的代价是它们的第一个元素——而这两个分割点可以是nums[1:]中的任意两个位置。所以问题等价于在 nums[1:] 中找最小的两个数。一次遍历维护最小和次小值就够了 ✅ 代码实现JavaclassSolution{publicintminimumCost(int[]nums){intfirstInteger.MAX_VALUE,secondInteger.MAX_VALUE;for(inti1;inums.length;i){if(nums[i]first){secondfirst;firstnums[i];}elseif(nums[i]second){secondnums[i];}}returnnums[0]firstsecond;}} 复杂度分析复杂度说明⏱️ 时间O(n)一次遍历 空间O(1)常数空间 参考灵茶山艾府 · 贪心算法题单 这题的关键洞察分割点的代价就是那个位置的元素值所以最优解就是找 nums[1:] 中最小的两个数。O(n) 一遍搞定击败 99.91%
