分割数组的最大值

410. 分割数组的最大值

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

示例 1：

输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。 
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

示例 2：

输入：nums = [1,2,3,4,5], m = 2
输出：9

示例 3：

输入：nums = [1,4,4], m = 3
输出：4

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 10⁶
1 <= m <= min(50, nums.length)

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int splitArray(vector<int>& nums, int m) { } };

rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-01-21 11:22:11

impl Solution {
    pub fn split_array(nums: Vec<i32>, k: i32) -> i32 {
        let check = |mx: i32| -> bool {
            let mut cnt = 1;
            let mut s = 0;
            for &x in &nums {
                if s + x <= mx {
                    s += x;
                } else { // 新划分一段
                    if cnt == k {
                        return false;
                    }
                    cnt += 1;
                    s = x;
                }
            }
            true
        };

        let mut right = nums.iter().sum::<i32>();
        let mut left = (*nums.iter().max().unwrap() - 1).max((right - 1) / k);
        while left + 1 < right {
            let mid = left + (right - left) / 2;
            if check(mid) {
                right = mid;
            } else {
                left = mid;
            }
        }
        right
    }
}

javascript 解法, 执行用时: 67 ms, 内存消耗: 49.6 MB, 提交时间: 2024-01-21 11:21:53

/**
 * @param {number[]} nums
 * @param {number} m
 * @return {number}
 */
var splitArray = function(nums, k) {
    function check(mx) {
        let cnt = 1;
        let s = 0;
        for (const x of nums) {
            if (s + x <= mx) {
                s += x;
            } else { // 新划分一段
                if (cnt++ === k) {
                    return false;
                }
                s = x;
            }
        }
        return true;
    }

    let right = _.sum(nums);
    let left = Math.max(Math.max(...nums) - 1, (right - 1) / k);
    while (left + 1 < right) {
        const mid = Math.floor((left + right) / 2);
        if (check(mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return right;
};

python3 解法, 执行用时: 7728 ms, 内存消耗: 18 MB, 提交时间: 2024-01-21 11:21:13

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        n = len(nums)
        f = [[10**18] * (m + 1) for _ in range(n + 1)]
        sub = [0]
        for elem in nums:
            sub.append(sub[-1] + elem)
        
        f[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, min(i, m) + 1):
                for k in range(i):
                    f[i][j] = min(f[i][j], max(f[k][j - 1], sub[i] - sub[k]))
        
        return f[n][m]

php 解法, 执行用时: 12 ms, 内存消耗: 19 MB, 提交时间: 2023-10-07 11:07:08

// 切割足够均匀
class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $m
     * @return Integer
     */
    function splitArray($nums, $m) {
        $left = max($nums);
        $right = array_sum($nums);
        while($left < $right){
            $mid = floor(($left+$right)/2);
            $sum = 0;
            $k = 0;
            foreach ($nums as $val){
                if(($sum + $val) > $mid){
                    $sum = $val;
                    $k = $k + 1;
                }else{
                    $sum = $sum + $val;
                }
            }
            if($sum <= $mid){
                $k = $k + 1;
            }
            if($k > $m){
                $left = $mid + 1 ;
    
            }else{
                $right = $mid;
            }
        }
        return $left;
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-10-07 11:04:44

func splitArray(nums []int, m int) int {
    left, right := 0, 0
    for i := 0; i < len(nums); i++ {
        right += nums[i]
        if left < nums[i] {
            left = nums[i]
        }
    }
    for left < right {
        mid := (right - left) / 2 + left
        if check(nums, mid, m) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func check(nums []int, x, m int) bool {
    sum, cnt := 0, 1
    for i := 0; i < len(nums); i++ {
        if sum + nums[i] > x {
            cnt++
            sum = nums[i]
        } else {
            sum += nums[i]
        }
    }
    return cnt <= m
}

python3 解法, 执行用时: 68 ms, 内存消耗: 15.9 MB, 提交时间: 2023-10-07 11:04:27

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        def check(x: int) -> bool:
            total, cnt = 0, 1
            for num in nums:
                if total + num > x:
                    cnt += 1
                    total = num
                else:
                    total += num
            return cnt <= m


        left = max(nums)
        right = sum(nums)
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1

        return left

java 解法, 执行用时: 0 ms, 内存消耗: 38.7 MB, 提交时间: 2023-10-07 11:04:10

class Solution {
    public int splitArray(int[] nums, int m) {
        int left = 0, right = 0;
        for (int i = 0; i < nums.length; i++) {
            right += nums[i];
            if (left < nums[i]) {
                left = nums[i];
            }
        }
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (check(nums, mid, m)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public boolean check(int[] nums, int x, int m) {
        int sum = 0;
        int cnt = 1;
        for (int i = 0; i < nums.length; i++) {
            if (sum + nums[i] > x) {
                cnt++;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
        }
        return cnt <= m;
    }
}

cpp 解法, 执行用时: 0 ms, 内存消耗: 7.5 MB, 提交时间: 2023-10-07 11:03:53

/**
 * 二分 + 贪心
 */
class Solution {
public:
    bool check(vector<int>& nums, int x, int m) {
        long long sum = 0;
        int cnt = 1;
        for (int i = 0; i < nums.size(); i++) {
            if (sum + nums[i] > x) {
                cnt++;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
        }
        return cnt <= m;
    }

    int splitArray(vector<int>& nums, int m) {
        long long left = 0, right = 0;
        for (int i = 0; i < nums.size(); i++) {
            right += nums[i];
            if (left < nums[i]) {
                left = nums[i];
            }
        }
        while (left < right) {
            long long mid = (left + right) >> 1;
            if (check(nums, mid, m)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

cpp 解法, 执行用时: 912 ms, 内存消耗: 9 MB, 提交时间: 2023-10-07 11:03:27

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int n = nums.size();
        vector<vector<long long>> f(n + 1, vector<long long>(m + 1, LLONG_MAX));
        vector<long long> sub(n + 1, 0);
        for (int i = 0; i < n; i++) {
            sub[i + 1] = sub[i] + nums[i];
        }
        f[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= min(i, m); j++) {
                for (int k = 0; k < i; k++) {
                    f[i][j] = min(f[i][j], max(f[k][j - 1], sub[i] - sub[k]));
                }
            }
        }
        return (int)f[n][m];
    }
};

java 解法, 执行用时: 104 ms, 内存消耗: 39.3 MB, 提交时间: 2023-10-07 11:03:10

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(f[i], Integer.MAX_VALUE);
        }
        int[] sub = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sub[i + 1] = sub[i] + nums[i];
        }
        f[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(i, m); j++) {
                for (int k = 0; k < i; k++) {
                    f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));
                }
            }
        }
        return f[n][m];
    }
}

golang 解法, 执行用时: 92 ms, 内存消耗: 3.1 MB, 提交时间: 2023-10-07 11:02:54

func splitArray(nums []int, m int) int {
    n := len(nums)
    f := make([][]int, n + 1)
    sub := make([]int, n + 1)
    for i := 0; i < len(f); i++ {
        f[i] = make([]int, m + 1)
        for j := 0; j < len(f[i]); j++ {
            f[i][j] = math.MaxInt32
        }
    }
    for i := 0; i < n; i++ {
        sub[i + 1] = sub[i] + nums[i]
    }
    f[0][0] = 0
    for i := 1; i <= n; i++ {
        for j := 1; j <= min(i, m); j++ {
            for k := 0; k < i; k++ {
                f[i][j] = min(f[i][j], max(f[k][j - 1], sub[i] - sub[k]))
            }
        }
    }
    return f[n][m]
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

上一题

下一题

详情