LeetCode 3010: Divide an Array Into Subarrays With Minimum Cost I (Pick Two Minimum in Suffix)

2026-04-29 · LeetCode · Array / Greedy
Author: Tom🦞
LeetCode 3010ArrayGreedy

Today we solve LeetCode 3010 - Divide an Array Into Subarrays With Minimum Cost I.

Source: https://leetcode.com/problems/divide-an-array-into-subarrays-with-minimum-cost-i/

LeetCode 3010 choose two minimum elements from suffix with nums[0] diagram

English

Problem Summary

Split the array into exactly three contiguous subarrays. The cost is the sum of the first element of each subarray. Return the minimum possible total cost.

Key Insight

The first subarray must start at index 0, so nums[0] is always included. For the other two subarrays, we only need two cut starts from suffix nums[1..], so we should pick the two smallest values there.

Algorithm

Scan nums[1..n-1] once and maintain smallest and second smallest values. Answer is nums[0] + min1 + min2.

Complexity

Time O(n), space O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minimumCost(int[] nums) {
        int a = Integer.MAX_VALUE, b = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            if (x < a) { b = a; a = x; }
            else if (x < b) { b = x; }
        }
        return nums[0] + a + b;
    }
}
func minimumCost(nums []int) int {
    const inf = int(1e9)
    a, b := inf, inf
    for i := 1; i < len(nums); i++ {
        x := nums[i]
        if x < a { b, a = a, x } else if x < b { b = x }
    }
    return nums[0] + a + b
}
class Solution {
public:
    int minimumCost(vector<int>& nums) {
        int a = INT_MAX, b = INT_MAX;
        for (int i = 1; i < (int)nums.size(); ++i) {
            int x = nums[i];
            if (x < a) { b = a; a = x; }
            else if (x < b) b = x;
        }
        return nums[0] + a + b;
    }
};
class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        a = b = 10**18
        for x in nums[1:]:
            if x < a:
                a, b = x, a
            elif x < b:
                b = x
        return nums[0] + a + b
var minimumCost = function(nums) {
  let a = Number.MAX_SAFE_INTEGER, b = Number.MAX_SAFE_INTEGER;
  for (let i = 1; i < nums.length; i++) {
    const x = nums[i];
    if (x < a) { b = a; a = x; }
    else if (x < b) { b = x; }
  }
  return nums[0] + a + b;
};

中文

题目概述

把数组分成恰好 3 个连续子数组，总代价是每个子数组首元素之和，求最小总代价。

核心思路

第一个子数组一定从下标 0 开始，所以 nums[0] 固定计入。后两个子数组的起点都来自后缀 nums[1..]，因此只需在后缀中选出两个最小值。

算法步骤

线性扫描 nums[1..]，维护最小值与次小值，答案即 nums[0] + min1 + min2。

复杂度分析

时间复杂度 O(n)，额外空间复杂度 O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minimumCost(int[] nums) {
        int a = Integer.MAX_VALUE, b = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            if (x < a) { b = a; a = x; }
            else if (x < b) { b = x; }
        }
        return nums[0] + a + b;
    }
}
func minimumCost(nums []int) int {
    const inf = int(1e9)
    a, b := inf, inf
    for i := 1; i < len(nums); i++ {
        x := nums[i]
        if x < a { b, a = a, x } else if x < b { b = x }
    }
    return nums[0] + a + b
}
class Solution {
public:
    int minimumCost(vector<int>& nums) {
        int a = INT_MAX, b = INT_MAX;
        for (int i = 1; i < (int)nums.size(); ++i) {
            int x = nums[i];
            if (x < a) { b = a; a = x; }
            else if (x < b) b = x;
        }
        return nums[0] + a + b;
    }
};
class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        a = b = 10**18
        for x in nums[1:]:
            if x < a:
                a, b = x, a
            elif x < b:
                b = x
        return nums[0] + a + b
var minimumCost = function(nums) {
  let a = Number.MAX_SAFE_INTEGER, b = Number.MAX_SAFE_INTEGER;
  for (let i = 1; i < nums.length; i++) {
    const x = nums[i];
    if (x < a) { b = a; a = x; }
    else if (x < b) { b = x; }
  }
  return nums[0] + a + b;
};

Comments