用經(jīng)典例題輕松幫你搞定貪心算法

轉(zhuǎn)自：奶糖貓

? ? ? ? ? ? ? ? ??? ???

貪心算法概念敘述

運(yùn)用貪心算法求解問題時(shí)，會(huì)將問題分為若干個(gè)子問題，可以將其想象成俄羅斯套娃，利用貪心的原則從內(nèi)向外依次求出當(dāng)前子問題的最優(yōu)解，也就是該算法不會(huì)直接從整體考慮問題，而是想要達(dá)到局部最優(yōu)。只有內(nèi)部的子問題求得最優(yōu)解，才能繼續(xù)解決包含該子問題的下一個(gè)子問題，所以前一個(gè)子問題的最優(yōu)解會(huì)是下一個(gè)子問題最優(yōu)解的一部分，重復(fù)這個(gè)操作直到堆疊出該問題的最優(yōu)解。

貪心算法最關(guān)鍵的部分在于貪心策略的選擇，貪心選擇的意思是對于所求問題的整體最優(yōu)解可以通過一系列的局部最優(yōu)選擇求得。而必須注意的是，貪心選擇必須具備無后效性，也就是某個(gè)狀態(tài)不會(huì)影響之前求得的局部最優(yōu)解。

運(yùn)動(dòng)貪心算法解決相應(yīng)問題時(shí)會(huì)比較簡單和高效，省去了尋找全局最優(yōu)解很多不必要的窮舉操作，由于貪心算法問題并沒有固定的貪心策略，所以唯一的難點(diǎn)就是找到帶求解問題的貪心策略，但畢竟熟能生巧嘛，算法的基本思想總是固定不變的。

貪心算法求解步驟

1. 將問題分解為若干個(gè)子問題

2. 找出適合的貪心策略

3. 求解每一個(gè)子問題的最優(yōu)解

4. 將局部最優(yōu)解堆疊成全局最優(yōu)解

下面通過利用貪心算法解決四道LeetCode題目，加深一下對貪心算法思想的掌握，其中第一道為easy，其余三道為medium，會(huì)標(biāo)注出相應(yīng)的題號。

455.分發(fā)餅干

問題描述：假設(shè)你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個(gè)孩子最多只能給一塊餅干。對每個(gè)孩子 i ，都有一個(gè)胃口值 gi ，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j ，都有一個(gè)尺寸 sj 。如果 sj >= gi ，我們可以將這個(gè)餅干 j 分配給孩子 i ，這個(gè)孩子會(huì)得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個(gè)最大數(shù)值。

注意：

• 你可以假設(shè)胃口值為正。

• 一個(gè)小朋友最多只能擁有一塊餅干

這道題的思路主要包括兩個(gè)點(diǎn)：

1. 盡量先滿足胃口值小的孩子，因?yàn)檫@樣的孩子容易滿足。

2. 進(jìn)行條件1時(shí)，盡可能選用尺寸小的，這樣大尺寸餅干可以用來滿足胃口值大的孩子。

這道題的貪心思想非常明顯，就是要盡可能地滿足更多的孩子，而胃口值小的孩子是容易滿足的，反之胃口值大的孩子很難滿足，所以在抉擇上盡可能滿足前者、餓著后者。

這個(gè)思想可以類比于賽馬，我們假設(shè)贏或者平作為滿足條件。如果A的3贏了B的1，那么剩下兩匹的結(jié)果可能就是一平一負(fù)或者兩負(fù)，那么此時(shí)至多才是1滿足；而如果A的馬和B的馬都按照順序比，則可以達(dá)到3平，那么此時(shí)可以達(dá)到3滿足。

所以綜上可以得到解題思路，首先需要將胃口值和餅干尺寸由小至大排序。設(shè)定一個(gè)計(jì)數(shù)器child，用來記得到滿足的孩子個(gè)數(shù)，再維護(hù)一個(gè)餅干指針cookies。如果餅干尺寸可以滿足孩子胃口值，即g[child]<=s[cookies]，就將child、cookies分別加一(向后移動(dòng)一位)，否則只將cookies向后移動(dòng)一位。因?yàn)楹⒆拥奈缚谥凳怯尚〉酱蟮?，若不滿足當(dāng)前的胃口值更不會(huì)滿足之后的。

55. 跳躍游戲

題目描述：給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達(dá)最后一個(gè)位置。

首先明確一下解題目標(biāo)，若要能夠到達(dá)最后一個(gè)位置，那么就需要最后一跳的最大距離加上該位置下標(biāo)一定要大于等于數(shù)組長度，即nums[i]+i>=length(nums)，而當(dāng)前元素又一定處于之前元素最遠(yuǎn)可以達(dá)到范圍之內(nèi)，這樣層層嵌套不就是貪心算法思想中的子問題的形式嘛。

我們要從數(shù)組的第一個(gè)元素開始遍歷，并且維護(hù)一個(gè)最遠(yuǎn)可以到達(dá)的位置(max_i)，當(dāng)遍歷到數(shù)組中的某一個(gè)位置i時(shí)，如果i在max_i范圍之內(nèi)，并且此時(shí)最遠(yuǎn)可以達(dá)到位置大于max_i，那么就通過i+nums[i]更新max_i，如果在遍歷過程中max_i大于等于數(shù)組長度，則代表可以達(dá)到最后一個(gè)位置，反之不能。要注意的是，max_i既不是數(shù)組下標(biāo)也不是數(shù)組中某個(gè)元素，而是二者的加和。

拿上面兩個(gè)示例為例：

• 示例1：最開始下標(biāo)為0的元素值為2，此時(shí)max_i=2，所以下標(biāo)1、2都在max_i之內(nèi)，當(dāng)達(dá)到下標(biāo)1時(shí)，此時(shí)max_i = 1+3 = 4，所以可以達(dá)到最后一個(gè)位置。

• 示例2：最開始下標(biāo)為0的元素值為3，此時(shí)max_i=3，下標(biāo)1、2、3在范圍內(nèi)，但在遍歷這三個(gè)位置時(shí)會(huì)發(fā)現(xiàn)max_i=2+1=1+2=0+3總是等于3，而3<4，所以最后一個(gè)位置永遠(yuǎn)達(dá)不到。

435.無重疊區(qū)間

題目描述：給定一個(gè)區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。

注意：

1. 可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)。

2. 區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。

本題的要求是“找到需要移出區(qū)間的最小數(shù)量”，換句話說就是要更多地保留集合中的區(qū)間，那么對于有重疊的區(qū)間，就應(yīng)該盡可能刪去跨度較大的區(qū)間。

這里我們根據(jù)區(qū)間的終點(diǎn)進(jìn)行貪心選擇，不是說起點(diǎn)不行，而是終點(diǎn)更好，那原因呢？因?yàn)?/span>如果每次選擇的區(qū)間結(jié)尾越小，留給后面區(qū)間的空間自然就變多了，那么后面能留下的區(qū)間數(shù)量也就越多。用一句話概括就是每次都選擇終點(diǎn)最小的，因?yàn)檫@一定是最優(yōu)解的一部分，這不就是正是貪心思想的應(yīng)用嘛。

解這道題時(shí)需要先將數(shù)組按照區(qū)間的終點(diǎn)進(jìn)行排序，然后需要維護(hù)一個(gè)end指針，它代表當(dāng)前集合中的最小終點(diǎn)，在遍歷數(shù)組時(shí)，若當(dāng)前元素的起點(diǎn)大于前一區(qū)間的終點(diǎn)，那么不重疊區(qū)間的計(jì)數(shù)器加一，更新end指針；反之則不做任何操作，最后區(qū)間總數(shù)減去不重疊區(qū)間即為需要移除區(qū)間的最小數(shù)量。

時(shí)間復(fù)雜度：一次排序加一次循環(huán)，。

LeetCode中第452題：用最少數(shù)量的箭引爆氣球與本題解法十分相似，大家可以類比本題的思路自己練習(xí)。

376. 擺動(dòng)序列

如果連續(xù)數(shù)字之間的差嚴(yán)格地在正數(shù)和負(fù)數(shù)之間交替，則數(shù)字序列稱為擺動(dòng)序列。第一個(gè)差（如果存在的話）可能是正數(shù)或負(fù)數(shù)。少于兩個(gè)元素的序列也是擺動(dòng)序列。

例如，?[1,7,4,9,2,5] 是一個(gè)擺動(dòng)序列，因?yàn)椴钪?(6,-3,5,-7,3)?是正負(fù)交替出現(xiàn)的。相反, [1,4,7,2,5]?和?[1,7,4,5,5] 不是擺動(dòng)序列，第一個(gè)序列是因?yàn)樗那皟蓚€(gè)差值都是正數(shù)，第二個(gè)序列是因?yàn)樗淖詈笠粋€(gè)差值為零。

給定一個(gè)整數(shù)序列，返回作為擺動(dòng)序列的最長子序列的長度。通過從原始序列中刪除一些（也可以不刪除）元素來獲得子序列，剩下的元素保持其原始順序。

示例1和示例3比較特殊，一個(gè)是完全擺動(dòng)序列，另一個(gè)是完全升序序列，所以這里利用比較普通的示例2講解，依據(jù)示例2中的數(shù)組可以大致繪制出一個(gè)元素分布圖，如下：

其中橙色點(diǎn)就構(gòu)成了一個(gè)擺動(dòng)序列，所以橙色點(diǎn)的個(gè)數(shù)也是最終要輸出的結(jié)果?？梢钥吹絒5,10,13,15]是一個(gè)連續(xù)遞增的子序列，5處于17之后是符合題意的，所以一定將其保留，而對于[10,13,15]三個(gè)元素，只有保留15才可以形成擺動(dòng)序列。

所以對于一段連續(xù)遞增的子序列，只有保留這段子序列的首尾元素時(shí)，才能形成一個(gè)擺動(dòng)序列，并且這也加大了尾部的后一個(gè)元素成為擺動(dòng)序列的下一個(gè)元素的可能性。同理連續(xù)遞減的子序列也做如上操作，比如圖中的[15,10,5]。

解決這道題的關(guān)鍵就在于如何保留連續(xù)連續(xù)遞增的子序列首尾元素，結(jié)合棧是一個(gè)很好的方法，但出棧入棧的條件是什么呢？我們維護(hù)一個(gè)狀態(tài)值nowstate，他共有"up"和"down"兩種取值，"up"表示該元素大于前一個(gè)元素，"dowm"表示該元素小于前一個(gè)元素。

從第二個(gè)元素開始遍歷數(shù)組，因?yàn)榈谝粋€(gè)元素(下標(biāo)為0)一定處于擺動(dòng)序列內(nèi)。若當(dāng)前元素大于前一個(gè)元素且nowstate="up"，這就說明連續(xù)遞增出現(xiàn)了，就需要從棧移除前一個(gè)元素。反之將nowstate更新為"up"，因?yàn)榇藭r(shí)前一個(gè)nowstate="down"，另一種可能性同理。不論什么條件下都要做入棧操作，因?yàn)檫@里只靠條件過濾不符合的元素。

總結(jié)

從上面幾道題中不難看出只要依據(jù)題意找出相應(yīng)的貪心策略，解題就十分容易，并且代碼也不復(fù)雜，但貪心選擇的方法并不唯一，主要還是靠對算法的理解和解題的經(jīng)驗(yàn)。貪心算法和動(dòng)態(tài)規(guī)劃是原理有些相似的兩種算法，同一問題利用不同算法解題的思路、難易程度各不相同，不要相互混淆。