leetcode 410题

leetcode 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

思路

这里使用二分查找的思路来实现，满足 x < [mid, max]，找到最终的 low 即是所求

代码

function splitArray(nums, m) {
  let sum = 0, maxNum = 0;

  for (const item of nums) {
    sum += item;
    if (item > maxNum) {
      maxNum = item;
    }
  }

  if (m === 1) {
    return sum;
  }

  let low = maxNum, high = sum;
  while (low < high) {
    const mid = Math.floor((high - low) / 2) + low;
    if (calSum(mid, m, nums)) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }

  return low;
}

function calSum(mid, m, nums) {
  let sum = 0, count = 0;

  for (const item of nums) {
    sum += item;
    if (sum > mid) {
      sum = item;
      count++;
      if (count > m-1) {
        return false;
      }
    }
  }
  return true;
}

复杂度分析:

时间复杂度: O(N)
空间复杂度：O(1)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python

leetcode 410 分割数组的最大值

思路

代码

CATALOG

FEATURED TAGS

FRIENDS