LeetCode 410. 分割数组的最大值

一、题目

1、题目描述

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

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

2、接口描述

​

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

3、原题链接

410. Split Array Largest Sum

---

二、解题报告

1、思路分析

看到”最大的最小“自然想到二分

那么关键就在于给定x，如何判断原数组是否能够划分为最大值不超过x的k个子数组

我们贪心地思考，如果原数组能够划分为最大值不超过x的j个子数组，j < k，那么一定也可以通过拆解某些子数组从而得到k个子数组

所以我们的check函数，遍历数组，贪心累加，如果sum > x，我们就cnt + 1，然后sum = x

最终取决于cnt <= k

很经典的二分+贪心的题目

2、复杂度

时间复杂度：O(n) 空间复杂度：O(1)

3、代码详解

class Solution {
public:int splitArray(vector<int>& nums, int k) {int r = 0 , l = 0;for(auto x : nums) r += x , l = max(l , x);function<bool(int)> check = [&](int t){int cnt = 1 , s = 0;for(auto x : nums){if(s + x > t)s = x , cnt++;elses += x;}return cnt <= k;};while(l < r){int mid = (l + r) >> 1;if(check(mid)) r = mid;else l = mid + 1;}return r;}
};