柚子快報邀請碼778899分享：【貪心算法】貪心算法一

http://yzkb.51969.com/

貪心算法一

1.檸檬水找零2.將數(shù)組和減半的最少操作次數(shù)3.最大數(shù)4.擺動序列

點贊??收藏??關(guān)注?? 你的支持是對我最大的鼓勵，我們一起努力吧!??

1.檸檬水找零

題目鏈接： 860. 檸檬水找零

題目分析：

這里有兩點需要注意：

顧客排隊購買你的產(chǎn)品一開始你手頭沒有任何零錢，你要拿著顧客的錢去找錢

顧客排隊購買你的產(chǎn)品，也就是說如果第一個顧客給你10或者20美元你就找不了，返回false。

算法原理：

這里我們只關(guān)注正確的貪心策略，不用管它怎么來的。最后我們來證明一下。

貪心可不是上來就貪，而是在分析問題的過程中，發(fā)現(xiàn)可以貪，我們才貪。

這道題就是一個找零問題，顧客會給5美元，10美元，20美元。我們分情況給他找錢就可以了。

當(dāng)顧客給5塊錢，我們直接收下就行了

當(dāng)顧客給10塊錢，我們要找5塊錢，順手把10塊錢收下，但是找5元前提是我們有5塊錢可以找，如果沒有返回false

當(dāng)顧客給20塊錢，關(guān)于20塊錢找零其實我們有兩種策略， 第一種：找一張10塊錢，在找一張5塊錢 第二種：找三張5塊錢

此時就有分歧了，我們要想哪一種最好，這就體現(xiàn)了貪心。貪心就體現(xiàn)在這一步，我們應(yīng)該選擇更優(yōu)的策略來完成這個找零工作。

到底那個優(yōu)秀，其實是根據(jù)5塊錢來的，5塊錢不僅完成20塊錢找零工作，還能完成10塊錢找零工作。因此我們盡量保留5塊錢。

所以看起來當(dāng)前最優(yōu)策略就是第一種策略。如果第一種策略不成立，我們再選第二種策略，如果第二種策略都不成立就返回false

class Solution {

public:

bool lemonadeChange(vector& bills) {

int five = 0, ten = 0;

for(auto e : bills)

{

if(e == 5) five++;

else if(e == 10)

{

if(five == 0) return false;

five--; ten++;

}

else

{

if(ten && five) //貪心

{

ten--; five--;

}

else if(five >= 3)

{

five -= 3;

}

else return false;

}

}

return true;

}

};

證明：貪心策略是正確的

證明策略：交換論證法

假設(shè) 貪心策略解決這道題的方法順序是：a、b、c、d、e、f， 最優(yōu)解解決這道題的方法順序是：e、b、c、d、a、f

此時如果在不破壞最優(yōu)解的 “最優(yōu)性質(zhì)的” 前提下，能夠?qū)⒆顑?yōu)解調(diào)整成貪心解。那我們就說貪心解就是最優(yōu)解。

這就是我們的交換論證法，交換論證法的核心就是找到不破壞最優(yōu)性質(zhì)的前提下把假設(shè)出來的最優(yōu)解逐步的調(diào)整出貪心解。

如果顧客給我們5美元或者10美元，貪心解和最優(yōu)解是沒有區(qū)別的。5塊就收下，10塊就找5塊。

唯一的區(qū)間就是20美元

貪心解策略是有限選擇10+5，但是最優(yōu)解有可能和貪心解不一樣選擇的是5+5+5。如果一樣肯定不考慮，考慮的肯定是不一樣的情況。

假設(shè)從左往右掃描第一次碰到20美元下不同的時候，我們看看能不能把最優(yōu)解調(diào)整成貪心解。

其實就盯著10美元就可以了。因為貪心解這里用到10，最優(yōu)解這里沒有用到10。那么此時10美元就有兩種情況了，第一種情況10美元在后面找零過程沒有用到，也就是貪心解用來10，但是最優(yōu)解在后面的找零操作并沒有用到10，10塊錢裝到兜里了。那么此時我們就可以把最優(yōu)解的兩個5替換成兜里的10塊錢。這個替換并不影響最優(yōu)性質(zhì)，因為這個10在后面找零操作就沒有用過。

最優(yōu)解能解決問題，替換完之后的10也能解決問題

第二種情況，10美元在后面的換零操作有一次用過了。此時我們依舊可以把前兩個5用后面的10交換。前面用10，后面用兩個5，交換后依舊不影響最優(yōu)性質(zhì)。然后又和貪心解一模一樣。

你會發(fā)現(xiàn)最優(yōu)解用或者不用10，都可以把它替換成和貪心解一樣的形式。也就說從前往后掃描只要不相等就調(diào)整，那最終一定能把最優(yōu)解逐步調(diào)整成貪心解，并且最優(yōu)解是可以解決問題，那貪心解也一定能解決問題。所以貪心解就和最優(yōu)解是等價的。

2.將數(shù)組和減半的最少操作次數(shù)

題目鏈接： 2208. 將數(shù)組和減半的最少操作次數(shù)

題目描述：

算法原理：

這道題把題意搞清楚之后，想讓我們用最少的操作次數(shù)把數(shù)組和至少減少到之前的一半，那我們肯定會想到每次挑選的時候挑選當(dāng)前數(shù)組里最大的數(shù)給它減半，因為挑數(shù)組最大的數(shù)減半才有可能最快的把整個數(shù)組的和減少到之前的一半。

解法：貪心

具體策略：每次挑選當(dāng)前數(shù)組中，最大的那個數(shù)，然后減半，直到數(shù)組和減少到至少一半為止。

實現(xiàn)我們這個策略的核心就是循環(huán)這一步，每次挑選當(dāng)前數(shù)組中，最大的那個數(shù)。如果每次都去遍歷數(shù)組挑最大的那個數(shù)，時間復(fù)雜度是非常恐怖的，這里我們可以使用優(yōu)先級隊列這個數(shù)據(jù)結(jié)構(gòu)建立一個大根堆。

解法：貪心 + 大根堆

class Solution {

public:

int halveArray(vector& nums) {

priority_queue heap;

double sum = 0.0;

for(auto e : nums)

{

heap.push(e);

sum += e;

}

sum /= 2.0;

int count = 0;

while(sum > 0)

{

double t = heap.top() / 2.0;

heap.pop();

sum -= t;

count++;

heap.push(t);

}

return count;

}

};

證明

證明策略：交換論證法

這里在說明一點，不管用什么方法證明，一定得要結(jié)合題意和貪心策略來證明。

我們這里的題意是每次挑選一個數(shù)直到數(shù)組和減半， 假設(shè)貪心解每次挑選數(shù)，這里用橫線上面的點表示每次挑選的數(shù)。同樣最優(yōu)解也是這樣表示。貪心解挑選的數(shù)個數(shù)大于或者等于最優(yōu)解的數(shù)個數(shù)。

我們只要能想到一個轉(zhuǎn)化規(guī)則，在不破壞最優(yōu)解的 “最優(yōu)性質(zhì)的” 前提下，能夠?qū)⒆顑?yōu)解調(diào)整成貪心解。就可以了。

那我們從左到右掃描貪心解和最優(yōu)解。先找到第一次兩者不一樣的地方。假設(shè)貪心解挑的是x，最優(yōu)解挑的是y，此時我們只要能把y變成x就可以了。

如何變，緊扣題意和貪心策略，在我們貪心解里面挑的數(shù)組中最大的數(shù)，最優(yōu)解如果沒有挑最大那個數(shù)，那么這里有一個不等式，x > y

對于x在最優(yōu)解中它有兩種情況，第一種情況，x沒有用過。此時可以大膽將y替換成x，因為x > y，你用一個小的數(shù)減半就能讓整個數(shù)組和減半，那選一個更大的數(shù)減半那更能讓整個數(shù)組和減半。即使后面有y/2，y/4等都可以用x替換y。

第二種情況，x在后續(xù)最優(yōu)解使用了，那我們依舊可以將y與x交換。因為在最優(yōu)解先用x減半和后用y減半并不影響最優(yōu)解的最少操作次數(shù)。即使在y和x中間可能使用了y/2，y/4，但是把y交換到后面去了，那就沒有y/2，y/4這些數(shù)，那邏輯不就錯了嗎。其實可以把y和x交換完之后，把y/2，y/4，y重新排一下序，還是 y，y/2，y/4的使用。

此時我們在處理最后一個情況，貪心解的次數(shù)可能是比最優(yōu)解次數(shù)多的，但是這種情況是絕對不可能的，因為我們從前往后掃描的時候，只要遇到不同都可以用這兩種情況進行調(diào)整。所以說當(dāng)最優(yōu)解解決完情況后，貪心解也一定減半了。所以最優(yōu)解的操作次數(shù)和貪心解的操作次數(shù)是一樣的。

到這里就證明完畢了。原因就是從前往后掃描兩個解的時候，只要有一個地方不一樣，就可以通過這兩個策略進行調(diào)整，所以最優(yōu)解就可以在不失去最優(yōu)性的前提下轉(zhuǎn)化為貪心解。所以當(dāng)最優(yōu)解是最少操作次數(shù)解決這個問題的時候，貪心解也是最少操作次數(shù)解決這個問題的時候。

3.最大數(shù)

題目鏈接： 179. 最大數(shù)

題目分析：

示例1，[10，2] 它所形成的最大整數(shù)就是這個數(shù)組里面按照從左往右的順序把數(shù)拼起來就可以了。比如這個數(shù)組不去休息順序從左往右拼起來就是102，如果調(diào)整一下順序拼接就是210，201顯然大于102，所以示例1所能拼成的最大整數(shù)就是210.

但是有可能輸出結(jié)果可能非常大，所以你需要返回一個字符串而不是整數(shù)。

算法原理：

如果把這道題的題意搞清楚之后會發(fā)現(xiàn)這道題特別像是一道排序題。無非就是給一個數(shù)組按照它給的規(guī)則把數(shù)組排下序使其形成一個最大的數(shù)。

所以先回憶之前正常的排序看能否給我們這道題帶來一些啟發(fā)

正常的排序（升序） [4，10，8]

不管是之前學(xué)習(xí)過的冒泡，快排，歸并等排序，它們都是干一件事情，就是確定這些元素的先后順序。只要能搞清楚這些元素誰在前面、誰在中間、誰在后面，我們就能完成這些元素的排序。

所以正常的排序本質(zhì)：確定元素的先后順序：誰在前，誰在后。

其中確定元素的先后順序是根據(jù)一定的排序規(guī)則來確定

本題的排序其實也是在確定元素的先后順序，所以我們僅需找一個排序規(guī)則就可以了。

排序規(guī)則，其實例一[10，2]已經(jīng)給我們了，先把這兩個數(shù)拼接成102和210，然后我們會發(fā)現(xiàn)把2放在前面把10放在后面是優(yōu)于102，因此我們得到一個結(jié)果把2放前面，10放后面。

我們可以把這兩個數(shù)抽象出來，a表示第一個數(shù)，b表示第二個數(shù)。 此時我們會得到兩種情況，要么a在前b在后，要么b在前a在后

如果發(fā)現(xiàn)a在前b在后這種拼接是優(yōu)于把b在前a在后的拼接，我們可以得到a可以放放在前面，b放在后面。

如果發(fā)現(xiàn)b在前a在后這種拼接和把a在前b在后的拼接是一樣的，那就無所謂。

如果發(fā)現(xiàn)b在前a在后這種拼接是優(yōu)于把a在前b在后的拼接，我們可以得到b可以放放在前面，a放在后面。

這就是我們這道題里面的排序規(guī)則?；谶@樣的排序規(guī)則會發(fā)現(xiàn)它們倆是非常一樣的，這里我們可以使用sort進行排序，然后把這個比較規(guī)則傳給sort。

我們這個專題不是貪心嗎，但是這里貪心體現(xiàn)在哪里呢？

其實貪心就體現(xiàn)在了比較規(guī)則，確定誰前誰后的策略就是貪心。

這一個排序規(guī)則，為什么能排序呢?

之前排序規(guī)則之所以能排序最重要的就是傳遞性。a > b，b > c ----> a > c，可以推出來 a 在 b 前面，b 在 c 前面，又因為 a > c，所以 a 在 c 前面。所以符合 a b c。

如果此時a > b，b > c 推不出來 a > c，就不能排序。因為a > b 可以推出 a 在 b 前面，b > c 可以推出 b 在 c 前面，如果推不出來 a > c 的意思是 c 可能大于 a，如果 c > a ，那 a 就在 c 的后面，此時根本就不可能。數(shù)組就不能排序。

上面?zhèn)鬟f性太明顯了，所以極有可能會忽略，但是我們這道題不能忽略這一點。如果知道 ab > ba，bc > cb 推出 a 在 b 的前面，b 在 c 的前面，如果在能知道ac > ca a 在 c 的前面，才能擺出 a b c

但是能不能推出這一點，需要后面去證明。

這里寫代碼還有兩個細(xì)節(jié)問題：

第一個細(xì)節(jié)：把數(shù)轉(zhuǎn)化成字符串，然后拼接成字符串，比較字典序。

如果不這樣搞還需要算兩個數(shù)有多少位，然后一個數(shù)乘于位數(shù)在加上另一個數(shù)才能得到一個拼接的數(shù)。

第二個細(xì)節(jié)：這道題有可能傳遞 [0，0]這樣的數(shù)組，如果按照之前的策略那就會返回一個 “00” 字符串。但是我們要的是一個數(shù)，我們要把字符串搞成 “0” 才行。我們可以判斷一下最后的結(jié)果ret，如果第一個字符是 “0” 說明后面應(yīng)該全都是 “0”，那我們最終返回 “0” 這個字符串就可以了。為什么后面應(yīng)該全都是 “0”，如果后面的是不是0的話，0放在最后一個位置絕對不可能是最大數(shù)。

class Solution {

public:

string largestNumber(vector& nums) {

// 優(yōu)化: 把所有的數(shù)轉(zhuǎn)化成字符串

vector strs;

for(int x : nums) strs.push_back(to_string(x));

// 排序

sort(strs.begin(), strs.end(), [](const string& s1, const string& s2)

{

return s1 + s2 > s2 + s1;

});

// 提取結(jié)果

string ret;

for(auto& s : strs) ret += s;

if(ret[0] == '0') return "0";

return ret;

}

};

證明：

這里我們只要證明我們這個策略是可以排序的就可以了。

如何證明一個東西可以排序呢？這里要用到數(shù)學(xué)的知識。

證明方法：數(shù)學(xué)知識（全序關(guān)系）

全序關(guān)系的用處：假設(shè)有一個集合，集合里有很多元素，全序關(guān)系的作用就是從這個集合中任意挑選兩個元素，如果這兩個元素在定義的比較規(guī)則下，如果滿足全序關(guān)系的話，我們就說這個集合是可以排序的。

全序關(guān)系分為三個性質(zhì)，也就是說只要滿足三個性質(zhì)就有全序關(guān)系。

完全性

從集合中任意挑選兩個元素 a、b，它必定會存在兩個關(guān)系的一個，要么 a <= b，要么 a >= b。如果挑選的兩個元素壓根沒有大小關(guān)系，根本不知道誰在前誰在后。所以完全性就是能夠排序的最前提條件：任意挑選兩個元素能夠比大小。

反對稱性

還是任意挑選兩個元素a、b，如果知道 a <= b 且 a >= b，那必須能夠推出 a = b，如果得不到這個結(jié)果，那么整個數(shù)組排序把a放在前面b放在后面是一種排序結(jié)果，把b放在前面a放在后面還是一種排序結(jié)果。那么整個集合就不能排序，因為整個集合要想排序那最終結(jié)果是唯一的才行。

傳遞性

任意挑三個元素a、b、c，如果 a >= b，b >= c，那一定要推出a >= c 。這一點上面已經(jīng)說過了如果不滿足排序不出來最終結(jié)果。

我們要證明的是排序規(guī)則，任意挑兩個數(shù)a、b，然后看 ab 和 ba 這個情況的大小，然后確定a和b的前后順序。

證明完全性

挑出a、b，然后看a拼接b，b拼接a是能夠比大小的就可以了。

第一種證明：

ab拼接后是一個數(shù)，ba拼接后也是一個數(shù)。數(shù)和數(shù)之間是能夠比大小的。要么ab >= ba，要么 ba >= ab。

第二種證明：

設(shè)a的位數(shù)為 x 位， b的位數(shù)為 y 位。 ab拼接的結(jié)果是可以表示出來的：10^ya + b ba：10^xb + a

既然這兩個數(shù)能明確表示出來，那一定能比大小。

證明反對稱性

如果 ab <= ba 且 ab >= ba，那我們要能得到 ab = ba 這個結(jié)論。

將ab和ba用剛才的進行處理，因為這里是一個一個的數(shù)，設(shè)ab為m，ba為n，此時我們能得到一個夾逼定理。m <= n <= m，我們可以得到 m = n。所以我們可以根據(jù)1、2得到3。

證明傳遞性

還是任取三個數(shù)a、b、c，如果ab >= ba 且 bc >= cb 我們必須要推出來ac >= ca ，ac >= ca的意思是a在前c在后，也就是說a在前，b在后，我們要能推出來a在前，c在后才行。

我們證明方法和上面一樣，把不等式寫成一個確切的數(shù)

這里特殊情況要考慮一下，如果a、b、c其中任意一個可能等于0， 假如a是0的話，那x位數(shù)就是為0。小學(xué)我們就知道0不是一個個位數(shù)，但是這道題里我們把0這個數(shù)當(dāng)成一個個位數(shù)。如a是12，b為0，ab為120

如果能由1和2這兩個式子能推出來第3個式子，那么這個式子就成立

我們觀察一下三個式子發(fā)現(xiàn)第三個式子是沒有b的，因此我們僅需通過1和2兩個式子把b給消掉就可以了。我們可以把b的系數(shù)移過去就可以把b消掉，但是移系數(shù)要注意系數(shù)不能為0，但是剛才處理特殊情況的時候說過x絕對不可能等于0的，那么10^x絕對不可能等于1，所以我們可以大膽移第一個式子b的系數(shù)。同樣第二個式子也是。

10^y - 1不可能為0，兩步同時消掉，然后在移項就可以得到第三個式子

到此證畢，我們這個排序規(guī)則既有完全性，又有反對稱性，又有對稱性，因此具有全序關(guān)系。有全序關(guān)系就說明我們這里定義的排序規(guī)則是可以排序的。

4.擺動序列

題目鏈接：376. 擺動序列

題目分析：

擺動序列就是一上一下。注意僅有一個元素或者含兩個不等元素的序列也視作擺動序列，返回擺動序列 的 最長子序列的長度。

算法原理：

這里我們就不寫具體的數(shù)了，而把數(shù)當(dāng)成折線圖的形式。目前先不考慮水平這樣的形式，先考慮相鄰兩個元素不同的形式，最后在把水平的處理一下

如果圖是這樣的，如何找它的最長擺動序列呢？ 我們肯定有這樣的想法，把左邊和右邊的點挑出來，然后在把所有極大值點和極小值點也挑出來，所形成的序列就是一個最長擺動序列。

這個策略確實是可以的，我們的貪心策略最終也和這個策略長的一樣。

接下來我們就來貪一下，我們要找到的是最長擺動序列，相當(dāng)于就是在這個圖中盡可能的挑一些點出來所形成的序列是擺動序列。

既然是盡可能挑多的點，那第一個點就給選上，接下來挑選第二個點的時候繼續(xù)貪，當(dāng)前右邊這么多點我選擇那個點看起來是最優(yōu)的，此時就有分情況討論的過程

第一種情況在上升的線上選一個點，但是在上升的這條線上選都沒有第三種情況好，因為選了上升線上一個點接下來要去選下降的，如果挑選這些較小上升的點，那在挑選下降的點可供選擇的空間就小了。比如畫×的點就選不到了。

第二種情況選擇右邊的某個點，如果選了這個點，那擺動系列絕對不可能是最長的，因為中間還有可以選擇的一上一下的點。

同樣選了這個點也會錯失一個拐點，那擺動序列也不會是最長的。

可能還會選這條下降線的點，有可能是會最長的，但是并不保險，有可能這條線沒有點，所以不如選第三種情況這個點。

固定兩個點之后，考慮第三個點依舊和選擇第二個點一樣分情況討論，如果是下降選擇不能在下降的點，如果是上升選擇不能在上升的點。直到所有點都選完，就是最長擺動子序列。

你會發(fā)現(xiàn)我們貪心挑選出來的點就是把極大值和極小值還有兩個端點的值跳出來。

貪心：統(tǒng)計出所有的波峰以及波谷的個數(shù) 然后在把左右兩個點加上就可以了。

那如何統(tǒng)計出最終的結(jié)果呢？

首先如何確定一個點是波峰還是波谷，

波峰：當(dāng)前這個點減左邊的點如果是正，右邊的點減去當(dāng)前的點如果是負(fù)，就是波峰。

波谷：當(dāng)前這個點減去左邊的點如果是負(fù)，右邊的點減去當(dāng)前的點如果是正，就是波谷。

也就是說當(dāng)前這個點左右是相反的就可以確定要么是波峰要么是波谷。

還有一個問題，如果相鄰兩個元素是相同的就麻煩了，它會分成兩大類， 第一類：相同的時候左右增減趨勢是相同的 第二類：相同的時候左右增減趨勢是相反的

第一類是沒有波峰波谷的，第二類是有的。雖然是有相同的元素，但是第一類總體要么上升、要么下降，不需要統(tǒng)計波峰波谷。第二類要么下降后上升、要么上升后下降，是需要統(tǒng)計波峰波谷的。

但是相同元素該統(tǒng)計那一個呢？并且雖然屬于不同類，但是都是左邊是是負(fù)數(shù)右邊是0一個不需要統(tǒng)計一個需要統(tǒng)計，還是很惡心的。

可以用一個變量left記錄當(dāng)前某個點左邊的增減趨勢，然后上述情況的時候，把這些相同的情況都可以忽略掉。僅需考慮最左邊點的增減趨勢和最右邊點的增減趨勢。

接下來模擬一下，

left就是標(biāo)記某個點左邊的正負(fù)，它有三種情況

left = 0（表示第一個點左邊既可以上升也可以是下降的） left > 0（上升） left < 0（下降）

然后確定某個點的時候僅需算一個它的右邊right就行了，right = nums[i+1] - nums[i] ，當(dāng)left*right <= 0 就是波峰或者波谷，當(dāng)right = 0 說明遇到相同的元素然后是可以拋棄的，

class Solution {

public:

int wiggleMaxLength(vector& nums) {

int n = nums.size();

if(n < 2) return n;

int left = 0, right = 0, ret = 0;

for(int i = 0; i < n - 1 ; ++i)

{

right = nums[i + 1] - nums[i];

if(right == 0) continue;

if(left * right <= 0) ++ret;

left = right;

}

return ret + 1;

}

};

證明：

這道題證明有三種方法：

反證法分類討論交換論證法

這里我們證明方法是反證法：

假設(shè)我們的操作是錯的，此時它的反命題就是一個正確的，只要我們證明正確的命題是有矛盾的或者有錯誤的，那原來的命題就是正確的。

我們的貪心解是選擇左右端點和極值，假設(shè)最后選擇的點為n，這里 n = 6

假設(shè)貪心解是錯的，那必須會存在一個最優(yōu)解，在相同的情況下可以選擇更多的點，N > 6。我們只要推出最優(yōu)解是矛盾的或者錯誤的，那我們貪心解就對了。

盯著每一個拐點，先看最左邊的拐點，我們這是一個連續(xù)的區(qū)間，左邊元素比它小，右邊元素也比它小，在它這個左右區(qū)間里一定會出現(xiàn)一個極大值，要么該點是極大值點要么就是區(qū)間內(nèi)的其他點。

在看下一個拐點，左右兩側(cè)都是比它大的，又因為是連續(xù)的，所以在這個區(qū)間里面必定會存在一個極小值。

同理后面也可以得到極大值，極小值。

因此可以推出在最優(yōu)解里，極值點個數(shù)是N-2（舍去左右兩端點），但是這個N-2是不存在的。因為在貪心解里面我們是可以推出來極值點個數(shù)是n-2=4，因為最優(yōu)解N>6，所以它的極值點個數(shù)是N-2 > 4的，但是極值點個數(shù)是不可能大于4的，所以最優(yōu)解壓根就是不存在的，因為貪心解得到極值點個數(shù)是4，你這個最優(yōu)解算出考慮極值點個數(shù)大于4，這是不符合實際情況的。所以這個最優(yōu)解是不存在的，因此貪心解是正確的。

柚子快報邀請碼778899分享：【貪心算法】貪心算法一

http://yzkb.51969.com/

好文鏈接