最大化最小值和最小化最大值
最小化最大值是為了壓制優(yōu)化目標(biāo)中表現(xiàn)最突出的成分，最大化最小值為了提升優(yōu)化目標(biāo)中表現(xiàn)最差的成分
關(guān)于這兩者的理解，我覺(jué)得這篇博文講得非常好，淺顯易懂又聯(lián)系實(shí)際。
理解問(wèn)題后，就要思考如何解決問(wèn)題。
記住，這兩類問(wèn)題一般都是用問(wèn)題轉(zhuǎn)換加二分查找的方法解決。
我會(huì)用代碼+詳細(xì)注釋的形式記錄這兩類問(wèn)題的解法，題目描述易于理解，耐心看完再看題解才會(huì)有收獲。
最大化最小值問(wèn)題：leetcode
你有一大塊巧克力，它由一些甜度不完全相同的小塊組成。我們用數(shù)組 sweetness 來(lái)表示每一小塊的甜度。
你打算和 K 名朋友一起分享這塊巧克力，所以你需要將切割 K 次才能得到 K+1 塊，每一塊都由一些 連續(xù) 的小塊組成。
為了表現(xiàn)出你的慷慨，你將會(huì)吃掉 總甜度最小 的一塊，并將其余幾塊分給你的朋友們。
請(qǐng)找出一個(gè)最佳的切割策略，使得你所分得的巧克力總甜度最大，并返回這個(gè) 最大總甜度。
?
示例 1：
輸入：sweetness = [1,2,3,4,5,6,7,8,9], K = 5
輸出：6
解釋：你可以把巧克力分成 [1,2,3], [4,5], [6], [7], [8], [9]。
示例 2：
輸入：sweetness = [5,6,7,8,9,1,2,3,4], K = 8
輸出：1
解釋：只有一種辦法可以把巧克力分成 9 塊。
示例 3：
輸入：sweetness = [1,2,2,1,2,2,1,2,2], K = 2
輸出：5
解釋：你可以把巧克力分成 [1,2,2], [1,2,2], [1,2,2]。
?
提示：
?? ?0 <= K < sweetness.length <= 10^4
?? ?1 <= sweetness[i] <= 10^5
?
題目描述中我用下劃線標(biāo)注出來(lái)的語(yǔ)句點(diǎn)明了這是一道最大化最小值的問(wèn)題。拋開(kāi)題目情景，這道題其實(shí)可以描述為：
給定一個(gè)數(shù)組，將數(shù)組分割成K+1個(gè)連續(xù)的子數(shù)組，求一種分割方法可以使得分割后的所有子數(shù)組的和的最小值，比其他分割方法得到的子數(shù)組的和最小值都大。要求輸出這個(gè)最大的最小值。
我們知道一個(gè)數(shù)組的子數(shù)組可以是它本身，也可以是一個(gè)只包含數(shù)組中任一元素的數(shù)組。所以我們可以求出數(shù)組的最小值（設(shè)為A）以及數(shù)組的和（設(shè)為B），那么我們要找的最大的最小值必定屬于[A,B)。
因此，問(wèn)題可以轉(zhuǎn)為在[A,B)中找到一個(gè)最大的數(shù)（最大化）使得存在一種分割方法可以讓所有子數(shù)組的和大于或等于這個(gè)數(shù)（最小值）。
由于[A,B)是有序的，所以在有序序列中找數(shù)，可以用二分查找。
那么如何找到上述的分割方法？
首先確定一點(diǎn)，這種分割方法要讓所有子數(shù)組的和大于或等于某個(gè)數(shù)（設(shè)為N），那么我們就要盡量讓其中的子數(shù)組的和與M的差值小一些。假設(shè)有一個(gè)子數(shù)組的和遠(yuǎn)遠(yuǎn)超過(guò)N，那就說(shuō)明其他子數(shù)組可以分到的元素很少，難以保證其他子數(shù)組的和也能超過(guò)M。這就像有時(shí)候我們?cè)诜峙湮镔Y一樣（前提是所有物資都必須分配完），在物資充足的情況下，我們說(shuō)要讓每個(gè)人都至少有N件物資，結(jié)果一開(kāi)始分配的時(shí)候就有一老哥上來(lái)拿走了遠(yuǎn)超過(guò)N件的物資然后就溜了，結(jié)果剩下的物資就難以保證每個(gè)人都至少有N件了，剩下的人肯定不愿意。所以一開(kāi)始分配給那位老哥的時(shí)候，我們就不能讓他自己拿，應(yīng)該一件一件地給他，給到N件了就讓他走人，這樣才能保證最后大家都有至少有N件。而如果一開(kāi)始物資就不足以讓每個(gè)人都至少有N件，那按照這個(gè)方法分到最后肯定有人沒(méi)有拿到N件物資。這樣的話，我們通過(guò)記錄多少人拿了N件物資，就能夠區(qū)分我們手頭的物資到底能不能讓每個(gè)人都至少有N件。
上面的描述轉(zhuǎn)換為我們討論的數(shù)組和子數(shù)組，就是對(duì)于第一個(gè)子數(shù)組，我們依次分配給它原數(shù)組的元素直到它的和超過(guò)了N，那我們就不分配了，開(kāi)始給第二個(gè)子數(shù)組分配了。最終看有多少個(gè)子數(shù)組的和大于或等于N。假設(shè)我們要求應(yīng)該有T個(gè)這樣的子數(shù)組，而實(shí)際上根據(jù)我們的分配得到的滿足要求的子數(shù)組的個(gè)數(shù)是M。若M>T，則說(shuō)明以N為最小值完全可以滿足我們的要求，N甚至可以再大些；若M<T，則說(shuō)明我們規(guī)定的N太大了，滿足不了這樣的分配，得把N設(shè)得小一點(diǎn)。M=T的情況可以歸到M>T中，在下面的代碼后會(huì)說(shuō)明（結(jié)合代碼說(shuō)比較清楚）。
鋪墊了這么多，可以寫代碼了：
class Solution { public:int maximizeSweetness(vector<int>& sweetness, int K) {int left=100005,right=0; //在[left,right)中通過(guò)二分查找尋找我們要的值for(int sw:sweetness){left=min(left,sw);right+=sw;}while(left<right){ //為避免出現(xiàn) (left+right)/2=left,然后cancut又一直返回true的情況，采用left+right+1int mid=(left+right+1)/2; //二分查找,mid就是我們每次給子數(shù)組的和設(shè)置的最小值if(cancut(sweetness,K,mid)){ //cancut=true,可以根據(jù)mid來(lái)切割，試試換個(gè)大一點(diǎn)的midleft=mid;}else{right=mid-1;}}return left;}//cuts:我們需要切割的次數(shù)；target:每個(gè)子數(shù)組的和要大于或等于target//返回值：true=target設(shè)置得太小了，再大點(diǎn)也能滿足要求；false則相反bool cancut(vector<int>& sweetness,int cuts,int target){int sum=0,cut=0; //sum記錄子數(shù)組的和, cnt記錄滿足要求的子數(shù)組的個(gè)數(shù)for(int sw:sweetness){sum+=sw;if(sum>=target){ //滿足要求了，割它sum=0; ++cnt;}if(cnt>cuts) return true;}return false;} };上面代碼中的cancut函數(shù)為什么不考慮cnt=cuts+1的情況（即達(dá)到要求的子數(shù)組個(gè)數(shù)與題目要求的個(gè)數(shù)相同）？這種情況下的target就是我們要找的最大化最小值嗎？
不是的，因?yàn)橛锌赡軘?shù)組的最后一個(gè)數(shù)組很大使得最后一個(gè)子數(shù)組的和超過(guò)2*target，那么實(shí)際上target還可以再設(shè)置為更大點(diǎn)。
?
最小化最大值問(wèn)題：leetcode
給定一個(gè)非負(fù)整數(shù)數(shù)組和一個(gè)整數(shù) m，你需要將這個(gè)數(shù)組分成 m 個(gè)非空的連續(xù)子數(shù)組。設(shè)計(jì)一個(gè)算法使得這 m 個(gè)子數(shù)組各自和的最大值最小。
注意:
數(shù)組長(zhǎng)度 n 滿足以下條件:
?? ?1 ≤ n ≤ 1000
?? ?1 ≤ m ≤ min(50, n)
示例:?
輸入:
nums = [7,2,5,10,8]
m = 2
輸出:
18
解釋:
一共有四種方法將nums分割為2個(gè)子數(shù)組。
其中最好的方式是將其分為[7,2,5] 和 [10,8]，
因?yàn)榇藭r(shí)這兩個(gè)子數(shù)組各自的和的最大值為18，在所有情況中最小。
?
這題題目描述已經(jīng)相當(dāng)明確了，沒(méi)有最大化最小值那題的情景設(shè)計(jì)。
我在一開(kāi)始說(shuō)過(guò)，這兩類問(wèn)題的基本思路是一樣的，核心是二分查找。看了上面我的那一大段最大化最小值的解釋后應(yīng)該很快能類比出這題的思路。
首先明確，要求的是“最大值”，其次才是最小化的最大值。那么假設(shè)原數(shù)組中最大的元素值為A，數(shù)組的和為B，那我們要求的這個(gè)最大值一定屬于[A,B)，所以我們?cè)赱A,B)中二分查找。
要使最大值最小，那么在分配子數(shù)組時(shí)我們應(yīng)該盡量讓每個(gè)子數(shù)組足夠的大。
還是拿分配物資來(lái)舉例。現(xiàn)在我們的目標(biāo)是讓分配給某個(gè)人的物資不能超過(guò)K件（前提是所有物資都必須分配完）。那么如果一開(kāi)始我們分配給前面的人的時(shí)候分配得很少，那么后面的人就越有可能分配到超過(guò)K件物資。因此我們要從一開(kāi)始就盡可能地多分配物資，但不超過(guò)K件。
回到數(shù)組中，即我們要讓第一個(gè)子數(shù)組盡可能的接近K但不超過(guò)K（可以等于，這時(shí)這個(gè)數(shù)組可能就是那個(gè)最小化最大值的子數(shù)組和了），當(dāng)再分配一個(gè)元素給第一個(gè)子數(shù)組時(shí)，其和超過(guò)K，那這個(gè)元素我們不分配給它，我們分配給第二個(gè)子數(shù)組，以此類推。
若最終分割到的子數(shù)組的個(gè)數(shù)為M，而我們要求的子數(shù)組的個(gè)數(shù)為T。當(dāng)M>T時(shí)，說(shuō)明有太多的子數(shù)組的和接近K，我們可以讓K再大一點(diǎn)，以減少M(fèi)。當(dāng)M<T時(shí)，說(shuō)明接近K的子數(shù)組和太少了，我們應(yīng)該讓K小一點(diǎn)，以來(lái)更多的子數(shù)組的和接近K。
下面的代碼采用long long做運(yùn)算是因?yàn)椴淮_定數(shù)據(jù)的取值范圍，怕發(fā)生整數(shù)溢出。
class Solution { public:int splitArray(vector<int>& nums, int m) {long long left=0,right=0;for(int num:nums) //取最大元素值和數(shù)組和left=max(left,(long long)num),right+=num;while(left<right){long long mid=(left+right)/2;if(cancut(nums,m-1,mid))right=mid;elseleft=mid+1;}return (int)left;}bool cancut(vector<int>& nums,int cuts,long long target){long long sum=0;int cnt=0;for(int num:nums){sum+=num;if(sum>target){ //target是預(yù)設(shè)的最大值，當(dāng)前子數(shù)組的和加上num之后超過(guò)了target，這是絕對(duì)不行的，所以我們?cè)诖税阉盍?#43;+cnt;sum=num; //然后把num分配給下一個(gè)子數(shù)組}if(cnt>cuts) //這就是M>=T的情況，至于>=為什么可以歸于一類，道理同最大化最小值最后我解釋的一樣return false;}return true;}};如果你要問(wèn)怎么上面代碼的二分就不用left+right+1，那你得好好溫習(xí)一下二分查找了，二分查找雖然簡(jiǎn)單，但有時(shí)候自己實(shí)現(xiàn)起來(lái)還說(shuō)不定bug重重，不斷TLE。
希望從此我能很快解決這兩類問(wèn)題！從理解到熟記于心！
總結(jié)
以上是生活随笔為你收集整理的最大化最小值和最小化最大值的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： LGBM函数及参数详解
- 下一篇： 腾讯云如何判断服务器是否中毒以及如何预防