leetcode410-分割数组的最大值

原题

给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)

示例:

输入:
nums = [7,2,5,10,8] m = 2

输出:
18

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

解法

思想

二分查找。要分成连续子数组,子数组的和的下限和上限分别是值最大的元素和所有元素之和,根据和不大于mid的子数组个数来逼近一个值,就是分割数组的最大值。

代码

class Solution {
    public int splitArray(int[] nums, int m) {
        int max = nums[0];
        int sum = 0;
        for(int i:nums){
            if(i>max) max = i;
            sum += i;
        }
        long start = max, end = sum;
        while(start<end){
            long mid = (start + end)/2;
            long temp = 0;
            int count = 1;
            for(int i:nums)
            {
                temp += i;
                if(temp>mid)
                {
                    temp = i;
                    ++count;
                }
            }
            if(count>m)
                start = mid + 1;
            else
                end = mid;
        }
        return (int)start;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode410-%e5%88%86%e5%89%b2%e6%95%b0%e7%bb%84%e7%9a%84%e6%9c%80%e5%a4%a7%e5%80%bc/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月9日
下一篇 2020年1月10日

相关推荐

  • leetcode62-不同路径

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月21日
    0370
  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0400
  • leetcode27-移除元素

    原题 给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(…

    算法 2019年11月20日
    080
  • 海量数据算法-BitMap介绍和实现

    作为一个有素质的程序员,在面试中(不是) 难免会遇到海量数据相关的问题,之前有注意过java.util下面有一个BitSet数据结构,但不是很明白是做什么用的。今天就来研究一下它背…

    算法 2020年2月27日
    03580
  • leetcode589-N叉树的前序遍历

    原题 给定一个 N 叉树,返回其节点值的前序遍历。 例如,给定一个 3叉树 : 返回其前序遍历: [1,3,5,6,2,4]。 说明: 递归法很简单,你可以使用迭代法完成此题吗? …

    2020年1月19日
    01030
  • leetcode454-四数相加II

    原题 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。 为…

    算法 2019年12月27日
    080
  • leetcode739-每日温度

    原题 根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定一个列表 te…

    算法 2019年12月11日
    0130
  • leetcode198-打家劫舍

    原题 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会…

    算法 2020年5月29日
    060
  • leetcode611-有效三角形的个数

    原题 给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。 示例1: 输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用…

    2020年2月8日
    070
  • 程序员面试金典08.11-硬币

    原题(来源Leetcode) 硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007) 示…

    算法 2020年4月23日
    0170

发表回复

登录后才能评论