遇到「最值问题」还在无脑动态规划？二分法考虑一下呗
目录
-
前言 -
二分法基础及变种结构 -
小试牛刀 -
打怪升级 -
出师试炼
前言
一般来说，遇到「最值问题」通用的方法都是动态规划，而有一类「最值问题」可以用其他方法更加巧妙、简单方便的解决，这类问题的常见问法是「使……最大值尽可能小」。
这类问题也是大厂笔试面试常见题型，2020 年美团笔试题、字节面试题中都出现过。
这类问题有三大特征：
-
求最值（一般是最小值） -
值的搜索空间是线性的 -
对该值有一个限制条件，并且若 x满足条件，则[x, +∞)都满足条件，反之(-∞, x]都不满足条件。
为了方便大家理解这类问题到底是个什么玩意儿，本汪在这里列出 leetcode 上的一道题目作为例子：
给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
不熟悉二分法的同学初遇此题，看到关键词“分割成 m 份”、“最小”，就想到了动态规划。诚然此题具备了使用动态规划的一切前提条件，也确实可以通过动态规划做出来，但其时间复杂度为 , 空间复杂度为 .
如果你看了本汪的这篇文章，学会了用二分法解决这一类问题，那么时间复杂度可以优化到 ， 空间复杂度可以优化到 ，并且思路非常简洁，代码实现也极其简单。
二分法基础及变种结构
在讲具体的方法之前，本汪先和大家一起回顾下二分法，熟悉二分法的同学可以直接跳过这部分。
最早接触二分思想的地方应该是在二分搜索中。（本质上类似快排中的 partition 思想）
二分法是在有序线性搜索空间内，利用有序性，每次搜索通过排除一半的剩余搜索空间，使 级别的线性搜索优化到 级别的方法。
二分法的基本代码非常简单，这里就不多提了，下面用类 java 语言给出其针对「最值问题」的变种结构：
// nums 数组是搜索空间，m 是限制条件
// check(x, m) 表示在搜索空间 nums 中的点 x，满足了限制条件 m
public int binary(int[] nums, int m){
初始化 l, r 为搜索空间的起始点和终点
while(l < r){
int mid = (l + r) >> 1; //二分，一次搜索可以排除 mid 的左边或者右边(剩余搜索空间的一半)
if(check(mid, m)) r = mid; //因为这一类最值问题要找的是最小，mid 满足条件了，(mid, r] 就不是最小的答案了
else l = mid + 1; // mid 不满足条件，根据有序性，[l, mid] 里的数全不满足条件
}
return r;
}
根据结构我们可以看出，遇到这类问题的时候只需要找到「搜索空间」、「检查条件」，然后套用结构就能轻轻松松地解决问题。
下面就让我们来用二分法解决刚刚提到的问题。
小试牛刀
题目
给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
思路
前文提及，解决本题只需要找到「搜索空间」、「检查条件」，剩下的就是闭着眼睛套结构的事儿了。
先找「搜索空间」，因为此类问题的搜索空间都是线性的，所以找到了起始点和终点，也就找到了搜索空间。
看问题描述 “子数组各自和的最大值最小”，也就是说我们搜索的点是 "子数组各自和的最大值"，那么搜索空间的起始点是数组 nums 中的最大值，即 min(nums)，搜索空间的终点是数组 nums 中的所有元素之和，即 sum(nums)。因此我们找到了搜索空间，为 [min(nums), sum(nums)].
再看「检查条件」。给定搜索空间 nums，和点 x，判断 x 是否满足限制条件 m。
本题的条件是“子数组各自和的最大值”，也就是说 x 和 m 个子数组各自和相比较，都要大于或者等于它们。
「搜索空间」、「检查条件」都找到了，下面闭着眼睛套结构吧～
代码
class Solution {
// 这个方法就是直接套结构
public int splitArray(int[] nums, int m) {
long l = 0, r = 0;
for(int num: nums) {r += num; l = Math.max(l, num);} // 初始化 l 和 r
while(l < r) {
long mid = (l + r) >> 1;
if(check(nums, mid, m)) r = mid;
else l = mid + 1;
}
return (int)r;
}
public boolean check(int[] nums, long a, int m) { // 给定搜索空间中的点 a，看它是否大于等于所有子数组的各自和
int cnt = 1;
long sum = 0;
for(int n: nums) {
sum += n;
if(sum > a) {
sum = n;
cnt ++;
if(cnt > m) return false;
}
}
return true;
}
}
打怪升级
咱们再来看一道题，小伙伴们可以先自己思考，有思路的话自己动手实现下。再看看本汪给出的思路，加深理解。
题目
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
思路
老规矩，先找「搜索空间」，再找「检查条件」，最后闭着眼睛套结构。
「搜索空间」：H 小时内必须吃完 sum(piles) 根香蕉，所以初始点为 sum(piles) / H，一次最多只能吃一堆，所以终点为 max(piles)。因此，搜索空间为 [sum(piles) / H, max(piles)]。
「检查条件」：“在 H 小时内吃掉所有香蕉”，因此以 K 个 / 小时 的速度吃完香蕉的用时要小于等于 H。
下面就闭着眼睛套结构吧。
代码
class Solution {
public int minEatingSpeed(int[] piles, int H) {
int l = 1, r = 0; // 这里本汪为了代码的简洁性，在不影响时间复杂度的情况下，直接让初始点为 1
for(int i: piles) r = Math.max(r, i); // 一次最多吃一堆
while(l < r){
int mid = (l + r) >> 1;
if(check(piles, mid, H)) r = mid;
else l = mid + 1;
}
return r;
}
boolean check(int[] piles, int K, int H){
int t = 0;
for(double i: piles){
t += Math.ceil(i / K); // 一堆香蕉共计 i 个，需要 ⌈i / K⌉ 个小时吃完
if(t > H) return false; // 警卫回来了还没吃完
}
return true;
}
}
出师试炼
我非常喜欢看我文章的小伙伴，个个都是人才，说话又好听，脑瓜子又聪明，还很主动的给我文章点赞。我相信砍翻两个小怪之后，你们已经是这类问题的专家了，下面就给几道题目供大伙随便玩玩。
关卡 1
你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0]并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。
关卡 2
牛牛有 n 件带水的衣服，干燥衣服有两种方式。
一、是用烘干机，可以每分钟烤干衣服的 k 滴水。
二、是自然烘干，每分钟衣服会自然烘干 1 滴水。
烘干机比较小，每次只能放进一件衣服。
注意，使用烘干机的时候，其他衣服仍然可以保持自然烘干状态，现在牛牛想知道最少要多少时间可以把衣服全烘干。
关卡 3
你太强了！我已经没有更多的题目给你玩了。你可以凭借这套武功闯荡江湖了！
……
……
……
等等，我说笑呢。你这小身板，要不先进我的其他训练营再练练呗？
啥，你问我的其他训练营在哪里？动动小手，点个关注，新的训练营已经在建设了，嘿嘿。