扔掉你的演算法書！1小時零基礎拿下貪心演算法！（17道題+萬字兒童級決議+數十張圖解）

前幾天的文章中我寫到了一些關于零基礎學習回溯演算法的一些步驟和細節，在刷題的程序中發現了很多貪心演算法的題很有趣，于是今天他來了，準備了好17道題來供大家共同學習，并附上了十分詳細的題解，與附帶了注釋的優美代碼，每個題的題解都可以說是隔壁牛大爺都看得懂了咯，相信聰明的小伙伴們一定可以快速上手拿下這個有趣的演算法思想，有點長，建議收藏反復觀看，文章附帶進度條！！可視化你的進步～

貪心演算法零基礎到快速變成高手

1.分發餅干

假設你是一位很棒的家長，想要給你的孩子們一些小餅干，但是，每個孩子最多只能給一塊餅干，
對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] ，如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足，你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值，

解題思路:
這是一道入門貪心演算法十分基礎的題目啦～
問題分析：首先我們要想滿足更多的孩子，是不是想著盡量用最小尺寸的小餅干去滿足孩子，這樣就能勻出來尺寸大的小餅干去滿足胃口比較大的孩子啦，
問題抽象：將兩個陣列進行排序，在同時掃描，
實作步驟：
1、排序兩個陣列，
2、掃描餅干尺寸陣列，如果能狗滿足胃口最小的，就將結果 + 1，并更新胃口陣列的下標，

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        int ans = 0;
        if (s.length == 0 || g.length == 0) return ans;
        // 使用Arrays類的方法，對陣列進行排序
        Arrays.sort(g);
        Arrays.sort(s);
        // 掃描兩個陣列（本質是掃描一個餅干尺寸陣列）
        for (int i = 0, j = 0; i < g.length && j < s.length; j ++) {
        	// 滿足 存在最小尺寸的餅干 給胃口最小的孩子
            if (s[j] >= g[i]) {
                ans ++;
                i ++;
            }
        }
        return ans;
    }
}

恭喜你入門啦，完成進度：

2.擺動序列

如果連續數字之間的差嚴格地在正數和負數之間交替，則數字序列稱為 擺動序列 ，第一個差（如果存在的話）可能是正數或負數，僅有一個元素或者含兩個不等元素的序列也視作擺動序列，
例如， [1, 7, 4, 9, 2, 5] 是一個 擺動序列 ，因為差值 (6, -3, 5, -7, 3) 是正負交替出現的，
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最后一個差值為零，
子序列 可以通過從原始序列中洗掉一些（也可以不洗掉）元素來獲得，剩下的元素保持其原始順序，
給你一個整數陣列 nums ，回傳 nums 中作為 擺動序列 的 最長子序列的長度 ，

解題思路:
問題分析：先明確題目中擺動序列的概念，要保證大概類似下圖的樣子：

不過要是針對題目中洗掉元素來獲得差值序列這種復雜的描述，我們可以更換一個新的思考方式，見下圖：

發現了如果存在這種“中間值”，我們需要刪掉，來保證陣列中的每個元素都屬于波峰或者波谷， 什么是波峰波谷呢？顧名思義 波峰就是在各點的兩邊的元素都比它小， 波谷就是兩邊都比它大， 這樣我們不需要洗掉元素，僅僅需要忽略過這種不是波峰波谷的值，在掃描陣列的時候根據坡度的變化來更新ans就可以咯，
問題抽象：
掃描陣列，根據差值確定是否更新ans值，
實作步驟：
1、定義currDiff表示當前元素與上一個元素的差值（也可以理解為坡度）
2、定義prevDiff表示上一個坡度，
3、遍歷陣列，坡度相反的時候，更新ans

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length <= 1) return nums.length;
        // 上一個坡度， 與 當前坡度初始化
        int prevDiff = 0, currDiff = 0, ans = 1;
        for (int i = 1; i < nums.length; i ++) {
            currDiff = nums[i] - nums[i - 1];
            // 當前坡度與上一個坡度相反，出現波峰或波谷
            if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
            	// 更新坡度
                prevDiff = currDiff;
                // 更新答案
                ans ++;
            }
        }
        return ans;
    }
}

恭喜你距離掌握貪心演算法又近了一步～

3.最大子序和

給定一個整數陣列 nums ，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，

解題思路:
問題分析：
剛剛接觸到這道題的時候，我們不難想出下面這樣的暴力思維：根據不同的起始位置掃描后面全部陣列元素，將最大值隨時記錄下來，于是就有了下面這種效率很低的暴力代碼：

int ans = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i ++) {
    int base = 0;
    for (int j = i; j < nums.length; j ++) {
        base += nums[j];
        ans = Math.max(ans, base);
    }
}

那么這道題可以優化成貪心的地方在哪里呢？ 仔細觀察我們的代碼，在外回圈每次更新的起始位置效率很低，每次只更新1，如果我們在掃描陣列元素的時候根據陣列元素的特性更新怎么樣呢？ 比如，當計數累加到遇到負數元素時，我們直接放棄當前序列（“拖油瓶”），遍歷后面的元素，并對答案保持更新，這樣，我們就少了一層確定起始位置的回圈，
問題抽象：
一層回圈控制陣列下標，遍歷的同時確定base是否舍棄，
實作步驟：
1、將最大值置為最小的整數值，用來更新后續最大值，
2、掃描陣列，base不斷累加當前元素，
3、如果base大于最大值，更新ans，
4、如果base累加到負數，立即舍棄“拖油瓶”，

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1) return nums[0];
        // 初始化變數
        int ans = Integer.MIN_VALUE, base = 0;
        for (int i = 0; i < nums.length; i ++) {
        	// 計數累加
            base += nums[i];
            // 時刻更新最大值
            ans = Math.max(ans, base);
            // 出現拖油瓶 立即舍棄
            if (base <= 0) base = 0;
        }
        return ans;
    }
}

恭喜你，更進一步

4.買賣股票的最佳時機II

給定一個陣列 prices ，其中 prices[i] 是一支給定股票第 i 天的價格，
設計一個演算法來計算你所能獲取的最大利潤，你可以盡可能地完成更多的交易（多次買賣一支股票），
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票），

解題思路:
問題分析：
給了股票每天的價格，想要賺錢，那肯定就是便宜的時候買入，漲價了就賣出咯，這個時候，就能看出來當買入(陣列元素)小于賣出(陣列元素)的時候就能累加到我們的答案中，但是應該什么時候賣呢？
[1, 5, 3] 這種情況很顯然在跌到3之前，火速先賣出去，賺一波大的
如果存在下面這種情況該怎么賣呢：
[1, 3, 5] 存不存在“小的”時候我先存著，等“大了”我在賣出去？我們不難發現，其實是一樣的，我們可以在1買入3賣出，同時3買入，5賣出，這樣子： [3 - 1 + 5 - 3] = 4 == [5 - 1] 是一樣的！！
這樣子問題就好辦了，我們只需要在上升的時候累加，下降的時候更新什么時候買入就好啦，只要不能賣錢的時候，我們就一直更新最低價格的時候再買入，
問題抽象：
掃描陣列，陣列元素上升時，做差累加，減少時，更新base，
實作步驟：
1、初始化base，即買入時候的價格，
2、掃描陣列，上升時候就賣出，
3、下降的時候更新base，即重置買入的價格，

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;
        // 初始化
        int ans = 0, base = prices[0];
        for (int i = 1; i < prices.length; i ++) {
        	// 有賺頭，火速賣掉
            if (prices[i] > base) {
                ans += prices[i] - base;
                base = prices[i];
              // 要虧了，不買不買，找到最便宜的時候買
            } else {
            // 注意這個位置，可以直接更新為最新值，因為如果存在比他大的，就直接賣掉了，不需要保持最小，
                base = Math.min(base, prices[i]);
            }
        }
        return ans;
    }
}

恭喜你，掌握了3分之1哦～

5.跳躍游戲

給定一個非負整數陣列 nums ，你最初位于陣列的 第一個下標 ，
陣列中的每個元素代表你在該位置可以跳躍的最大長度，
判斷你是否能夠到達最后一個下標，

解題思路:
問題分析：
根據題目描述，我們要想跳到終點，需要怎么跳才能跳過去呢？怎么確定一次到底跳幾個格子呢？ 這樣子想，問題就想復雜了！其實跳到哪里都無所謂，每次跳躍其實都只是獲得了你最遠能跳到哪里的資訊，如圖：

不難發現通過遍歷可以跳到位置的時候每次更新可以跳到的最遠距離，如果最遠距離可以達到最后元素的位置，我們就可以直接回傳，
問題抽象：
在可以跳到的最遠距離內掃描陣列，時刻更新最大距離，滿足條件即回傳true，如果掃描完，說明最大距離無法達到陣列末端，回傳false，
實作步驟：
1、初始化最遠距離maxDist為nums[0]，
2、在最遠距離范圍內逐步掃描陣列，并更新最遠距離，
3、判斷如果最遠距離大于陣列長度，回傳true，
4、回傳false，

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1) return true;
        // 初始化
        int maxDist = nums[0], jumpDist = 0;
        // 最遠距離內逐步掃描
        for (int i = 0; i <= maxDist; i ++) {
        	// 判斷是否滿足條件
            if (maxDist >= nums.length - 1) return true;
            // 更新最遠距離
            maxDist = Math.max(maxDist, i + nums[i]);
        }
        return false;
    }
}

繼續努力哦～

6.跳躍游戲II

給定一個非負整數陣列，你最初位于陣列的第一個位置，
陣列中的每個元素代表你在該位置可以跳躍的最大長度，
你的目標是使用最少的跳躍次數到達陣列的最后一個位置，
假設你總是可以到達陣列的最后一個位置，

解題思路:
問題分析：
這道題和上一道題有一點點不一樣，要求回傳的是最少的跳躍次數，這個時候可讓大家絞盡了腦汁，該怎么確定啥時候計數器+1呢；不慌不慌，看看這個圖就一目了然啦：

不難發現通過遍歷可以跳到當前步數內最遠位置的時候每次更新步數和下一個步數內可以跳到的最遠距離，如果最遠距離可以達到最后元素的位置，我們就可以直接回傳，
問題抽象：
逐步掃描，在可以跳到當前步數內的最遠距離時，更新步數和下一個步數內可以到達的最遠距離，如果最遠距離可以到達陣列長度，回傳步數，
實作步驟：
1、初始化最遠距離maxDist為0，當前步數可以跳到的最遠距離currDist為0，
2、在currDist范圍內更新maxDist，確定下一個步數內的maxDist，
3、到達currDist時候更新步數，判斷下一個步之內能否到達終點，
4、回傳步數，

class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1) return 0;
        // 初始化步數
        // 下一個步數可以到達的最遠距離
        // 當前步數內可以到達的最遠距離
        int ans = 0, maxDist = 0, currDist = 0;
        for (int i = 0; i < nums.length; i ++) {
        	// 當前步數內確定下一步一步之內能跳到的最遠距離
            maxDist = Math.max(maxDist, i + nums[i]);
            // 跳到當前步數能到達的最大位置了
            if (i >= currDist) {
            	// 更新步數
                ans ++;
                // 更新下一步能跳到的最遠距離
                currDist = maxDist;
                // 滿足條件，回傳
                if (maxDist >= nums.length - 1) return ans;
            }
        }
        return ans;
    }
}

掌握一半啦！你已經超過全世界一半的人啦～

7.K次取反后最大化的陣列和

給定一個整數陣列 A，我們只能用以下方法修改該陣列：我們選擇某個索引 i 并將 A[i] 替換為 -A[i]，然后總共重復這個程序 K 次，（我們可以多次選擇同一個索引 i，）
以這種方式修改陣列后，回傳陣列可能的最大和，

解題思路:
問題分析：
這是一道簡單題，根據題目要求，可以對多次同一個索引操作，我們可以知道，如果在一個陣列中經過k次取相反數后能夠獲得最大sum，必須將最小的值進行取相反數，這樣子如果是負數，那么sum增大的越多，如果是正數，那么扣除的就越少，我們采用這種貪心的方式后，如果條件是比較復雜的情況該怎么處理呢，下面給出一個較為一般化的例子來分析：
[1, -2 , 3, -1, 2, -3] K = 5,首先將這個復雜的陣列排序，如圖：

此時按照我們正常人的思考方式，肯定是將絕對值最大的負數進行反轉，如果將所有負數都反轉后k還有盈余，這時候就可以對絕對值最小的那個數字進行不斷的翻轉，以求得最大的sum，思路理清了，后面就是將解法轉換成程式語言，
問題抽象：
排序陣列后，在k次操作內，如果陣列中存在負數，就對最小的負數進行不斷取相反數，沒有盈余就結束，有盈余就對絕對值最小的數字進行操作，
實作步驟：
1、排序陣列
2、k次遍歷陣列，在范圍內將最低值進行取相反數
3、如果有負數，就取相反數，
4、與下一位數的絕對值進行比較，來決定是否更新 index

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int sum = 0;
        // 需要對陣列元素取相反數的index
        int index = 0;
        for(int i = 0; i < k; i ++) {
        	// 遇到負數
            if (nums[index] < 0 && i < nums.length - 1) {
            	// 直接取反
                nums[index] = - nums[index];
                // 將index控制在絕對值最小的陣列元素上
                if (nums[index] >= Math.abs(nums[index + 1])) index ++;
                continue;
            }
            // 非負數直接取相反數
            nums[index] = - nums[index];
        }
        for (int i = 0; i < nums.length; i ++) sum += nums[i];
        return sum;
    }
}

加油加油，堅持就是勝利！

8.加油站

在一潭訓路上有 N 個加油站，其中第 i 個加油站有汽油 gas[i] 升，
你有一輛油箱容量無限的的汽車，從第 i 個加油站開往第 i+1 個加油站需要消耗汽油 cost[i] 升，你從其中的一個加油站出發，開始時油箱為空，
如果你可以繞環路行駛一周，則回傳出發時加油站的編號，否則回傳 -1，
說明:
1、如果題目有解，該答案即為唯一答案，
2、輸入陣列均為非空陣列，且長度相同，
3、輸入陣列中的元素均為非負數，

解題思路:
問題分析：
根據題意，有兩種情況，一種是存在這么一個加油站，使得可以完成一圈，另一種就是無法跑完一圈，那么如何界定能否跑完呢？我們可以這樣想，把所有加油站的油都加起來，如果比所有需要的油加起來還多，那肯定就是能跑完了，只不過就是在哪里開始出發的問題啦，這樣我們進入能跑完的分支，我們就得分析分析你跑完一個路程，所加上的油能否比消耗的油多，至少不能路上拋錨吧，所以我們需要記錄車里所剩余的油量，通過它的正負來判斷一開始選的位置能否滿足跑一圈的需求，如果不滿足，我們就根據當前加油站的位置，更換新的起點，
問題抽象：
遍歷陣列的同時記錄當前剩余的油量是否為正數，并依次來更新，出發點的位置，同時還需要記錄總油量的差值，如果跑完一圈下來總油量是負的，那就說明跑不完，回傳-1
實作步驟：
1、定義rest 當前剩余油量，totalGas總剩余油量，index記錄出發點，
2、遍歷兩個陣列，記錄差值為當前一趟所剩余的油量，累加到當前剩余油量以及總剩余油量，
3、如果當前剩余油量為負，更換起點，當前油量置0，
4、最后，如果總油量小于0，回傳-1；否則回傳起點，

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        // 初始化油量
        int rest = 0, totalGas = 0;
        int index = 0; // 記錄出發地點
        for (int i = 0; i < n; i ++) {
	        // 計算從出發地點開始所剩余的油量
            rest += gas[i] - cost[i]; 
            // 計算從計位點0開始所剩余的總油量
            totalGas += gas[i] - cost[i];
            // 選點錯誤，更換出發地點
            if (rest < 0) {
                index = (i + 1) % n;
                rest = 0; // 新出發地開始的油量置空
            }
        }
        if (totalGas < 0) return -1; // 無法跑完行程
        return index;
    }
}

馬上就掌握三分之二啦～

9.分發糖果

老師想給孩子們分發糖果，有 N 個孩子站成了一條直線，老師會根據每個孩子的表現，預先給他們評分，
你需要按照以下要求，幫助老師給這些孩子分發糖果：
1、每個孩子至少分配到 1 個糖果，
2、評分更高的孩子必須比他兩側的鄰位孩子獲得更多的糖果，
那么這樣下來，老師至少需要準備多少顆糖果呢？

解題思路:
問題分析：
leetcode上標了困難題，那么這道題難在哪里呢，難在它的貪心策略上，我們如果從頭開始遍歷數字，既要考慮這個數字會不會比左邊大，又要考慮這是數字會不會比右邊大，大家可以清晰的感覺到，啊，好難決策，萬一后面的都很小呢，又要回過頭來修改前面的數，簡直難受到爆，那么根據這種情況，我們換一種思路，采用貪心策略中：多個區域最優解組成全域最優解的性質–> 采用左視角和右視角，只要兩個視角都符合條件，那么結果一定符合條件，因為題目中僅有兩點要求，第一點每個人都要有糖，用來初始化，第二點就是用來用來確定左右時圖中的模樣，有點像搭積木一樣，左視圖：保證后面越大，發的越多，小的看不見的就略過并重新開始搭積木，右視圖：從小開始搭積木，遇到大的和自己看到的和左視圖的拿來比較取最大的那個（否則將破壞左視角的最優區域解），
問題抽象：
陣列賦1，遍歷評分陣列，升序+1，降序置1重新升序，倒敘遍歷評分陣列，與升序陣列比較，插入，
實作步驟：
1、將糖果陣列賦1
2、遍歷評分陣列，如果后面的比前面的大，就讓后面的是前面的糖果樹+1
3、倒序遍歷陣列，如果前面的比后面的大，就讓前面的是后面的糖果數加1 或者 為從步驟2中得到的更大的數字，

class Solution {
    public int candy(int[] ratings) {
        int ans = 0;
        // 初始化，并賦1
        int[] candies = new int[ratings.length];
        for (int i = 0; i < candies.length; i ++) candies[i] = 1;
        // 左視圖遍歷
        for (int i = 1; i < ratings.length; i ++) {
            if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
        }
        // 右視圖遍歷
        for (int i = ratings.length - 2; i >= 0; i --) {
            if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1); // 同時滿足左視圖
        }
        // 相加結果
        for (int i = 0; i < candies.length; i ++) {
            ans += candies[i];
        }
        return ans;
    }
}

掌握三分之二啦～

10.檸檬水找零

在檸檬水攤上，每一杯檸檬水的售價為 5 美元，
顧客排隊購買你的產品，（按賬單 bills 支付的順序）一次購買一杯，
每位顧客只買一杯檸檬水，然后向你付 5 美元、10 美元或 20 美元，你必須給每個顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元，
注意，一開始你手頭沒有任何零錢，
如果你能給每位顧客正確找零，回傳 true ，否則回傳 false ，

解題思路:
問題分析：
這種找錢型別的題，應該是我們人類最熟練處理的貪心問題了吧，大家在找錢的時候肯定是先找最大的，然后在找最小的吧，（如果不是，那可能就有點尷尬了），這樣找錢可以確保找的錢的數量最少，這道題的找錢的那個抽屜里面只有5美元，10美元，根據顧客給錢的數量大致可以這樣分為三個情況：
1、顧客給你5塊： 欣然收下，5塊個數 ++；
2、顧客給你10塊：還可以，找他5塊，5塊個數 --，10塊個數++；
3、顧客給你20塊：很煩，找他10+5，或者5+5+5；分別10塊個數-- 5塊個數-- 和 5塊個數 -= 3
明確了思路，答案其實已經就出來了，那么這道題的貪心策略在哪里呢？大家在做的時候可能不以為然的就做出來了而感覺沒有用到貪心，其實這里的貪心在第三種情況，給你20的時候，你該怎么找錢，我們發現情況2，和情況3都必須使用5塊的，為了不讓5塊的出現不夠的情況，在第三種情況出現的時候我們選擇找錢的時候，將只有第三種情況才會使用的10塊錢先找給他，在找給他1個5塊就可以了，能保證讓“最有價值”的5塊盡可能少的消耗，區域最優使得全域最優，
問題抽象：
遍歷bills陣列遇到5塊就加，遇到10塊，判斷后，減5個數，加10個數，遇到20塊，邊找錢，邊判斷回傳，
實作步驟：
1、初始化5塊、10塊的個數，
2、遍歷bills陣列：三種情況：

• 如果是5塊，就給5塊錢的個數+1，
• 如果是10塊，就找去5塊錢，并給10塊錢個數+1，
• 如果是20塊，就先找10塊，在找5塊，

class Solution {
    public boolean lemonadeChange(int[] bills) {
    	// 初始化5、10塊的數量
        int cent5 = 0, cent10 = 0;
        for (int i = 0; i < bills.length; i ++) {
        	// 5塊直接拿下！
            if (bills[i] == 5) cent5 ++;
            // 10塊找他5塊
            if (bills[i] == 10) {
                if (cent5 == 0) return false;
                cent5 --;
                cent10 ++;
            }
            // 20塊
            if (bills[i] == 20) {
            	// 沒有5塊還想找錢？？
                if(cent5 == 0) return false;
                // 有10塊就先上大的！！
                if(cent10 > 0) {
                    cent10 --;
                    cent5 --;
                } else {
                    cent5 -= 3;
                    if (cent5 < 0) return false;
                }
            }
        }
        return true;
    }
}

掌握了四分之三了，你是最棒的！！！

11.根據身高重建佇列

假設有打亂順序的一群人站成一個佇列，陣列 people 表示佇列中一些人的屬性（不一定按順序），每個 people[i] = [hi, ki]表示第 i 個人的身高為 hi ，前面 正好 有 ki 個身高大于或等于 hi 的人，
請你重新構造并回傳輸入陣列 people 所表示的佇列，回傳的佇列應該格式化為陣列 queue ，其中 queue[j] = [hj, kj] 是佇列中第 j 個人的屬性（queue[0] 是排在佇列前面的人），

解題思路:
問題分析：
看了題目有點懵，不要慌，我們可以通過示例來了解題意，其實示例就展現的很清楚了，將一個已經排好序的人群佇列的身高和參考值 k 記錄下來，隨后進行打亂，讓我們根據每個人的 [hi, ki] 將佇列還原，這道題和我們上一道題有共通之處的就是，hi 和 ki 這樣的兩個參考點是相互制約的，我們無法通過一次遍歷，就將問題處理的十分完美，這道題的貪心思想是什么呢？ 我們在排序的時候可以根據身高進行第一波篩選，遇到身高相同的時候，我們根據 k 進行第二波篩選，這里，我們可以重寫陣列的比較器 Comparator，來實作我們自己的比較規則，然后進行排序：如果身高不同就將高的排在后面， 如果身高相同就將 k 大的排在后面，
問題抽象：
根據身高進行升序排序，在身高相同時，根據k進行降序排序，保證符合題目要求

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] person1, int[] person2) {
            	// 如果身高不同
                if (person1[0] != person2[0]) {
                	// 按照身高升序排列
                    return person2[0] - person1[0];
                } else {
                	// 身高相同 按照k降序排列
                    return person1[1] - person2[1];
                }
            }
        });
        LinkedList<int[]> que = new LinkedList<>();
        // 將我們排列后的人加入佇列
        for (int[] p : people) {
            que.add(p[1], p);
        }
        // 回傳
        return que.toArray(new int[people.length][]);
    }
}

加油加油！！

12.用最少數量的箭引爆氣球

在二維空間中有許多球形的氣球，對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結束坐標，由于它是水平的，所以縱坐標并不重要，因此只要知道開始和結束的橫坐標就足夠了，開始坐標總是小于結束坐標，
一支弓箭可以沿著 x 軸從不同點完全垂直地射出，在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結束坐標為 xstart，xend， 且滿足 xstart ≤ x ≤ xend，則該氣球會被引爆，可以射出的弓箭的數量沒有限制， 弓箭一旦被射出之后，可以無限地前進，我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數量，
給你一個陣列 points ，其中 points [i] = [xstart,xend] ，回傳引爆所有氣球所必須射出的最小弓箭數，

解題思路:
問題分析：
根據題目描述，想射穿越多的氣球，肯定要在氣球最密集的地方射箭啦：看下面這張圖：

圖中這一支箭射了4個，如何來找到這么一支箭呢？我們先人肉模擬一下這個程序，見下面這個圖：

在起點這里可以保證射穿1個，然后繼續向右邊掃描

在第一個氣球的范圍內可以射到第二個了！繼續向右掃描

找到解啦～，回顧我們的掃描程序，我們是如何掃描的？我們在第一個碰到的氣球的屁股的范圍內一直掃描，將碰到的氣球都射穿，之后在化歸到起始步驟就可以咯，這就是我們的貪心策略，那么如何操作呢？首先將氣球按照氣球的終點進行排序，這樣，我們遍歷的時候，就可以對第一個氣球終點之前的氣球進行操作了，如果下一個氣球的起點超過了第一個氣球的終點，說明無法一支箭射穿，弓箭數量++，更新下一支箭的位置，
問題抽象：
將氣球按照氣球屁股的位置進行排序，從頭開始掃描，在每個屁股的范圍內射穿盡可能多的氣球，超過第一個氣球的范圍就更新箭的位置和數量，
實作步驟：
1、根據氣球的終點位置升序排序，
2、確定第一支箭的位置，
3、掃描氣球，通過起始位置，更新下一支箭范圍，

class Solution {
    public int findMinArrowShots(int[][] points) {
        int n = points.length, ans = 1;
        // 根據終點位置排序
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] point1, int[] point2) {
                if (point1[1] > point2[1]) {
                    return 1;
                } else if (point1[1] < point2[1]) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });
        // 第一支箭在屁股最靠前的第一個氣球的屁股上
        int arrow = points[0][1];
        for (int i = 1; i < n; i ++) {
        	// 如果后面的氣球的頭在前面氣球屁股的后面，就更新
            if (points[i][0] > arrow) {
                ans ++;
                // 下一個箭更新到下一個氣球的屁股
                arrow = points[i][1];
            }
        }
        return ans;
    }
}

你八成能拿下所有貪心的題目了！

13.無重疊區間

給定一個區間的集合，找到需要移除區間的最小數量，使剩余區間互不重疊，
注意:
1、可以認為區間的終點總是大于它的起點，
2、區間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊，

解題思路:
問題分析：
這道題和上一道題很類似，依然是通過區間終點來進行升序排序，至于為什么這么做，這就涉及到數學中對這個問題進行嚴格的推理和歸納總結了，有興趣的小伙伴自己下去進行嘗試叭～ 可以將結果分享在評論區哦～ 只需要記住，很多區間類的貪心策略都是根據區間的終點進行升序排序的就好，排序完掃描如果遇到下一個區間的起點在上一個區間終點的前面就把這個去掉并統計，如果下一個區間的起點在上一個區間終點的后面，就更新后面的區間終點為最新的“屁股”，畫個圖來理解一下：

問題抽象：
根據區間終點的位置進行升序排序，根據下一個區間的起點更新答案，
實作步驟：
1、根據區間終點的位置進行升序排序，
2、確定第一個區間的終點位置，
3、掃描區間，如果后面區間的起點在前面區間的終點之前就去掉，更新答案，
4、如果后面的起點在前面終點的后面，就更新起點，

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
    	// 根據區間的屁股進行升序排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                if (interval1[1] > interval2[1]) return 1;
                if (interval2[1] > interval1[1]) return -1;
                else return 0;
            }
        });
        // 去掉的區間的數量
        int count = 0;
        // 第一個區間的終點位置
        int right = intervals[0][1];
        for (int i = 1; i < intervals.length; i ++) {
        	// 如果下一個區間起點在上一個區間終點之前就去掉
            if (intervals[i][0] < right) {
                count ++;
            } else {
            	// 下一個區間起點在上一個區間終點后面就更新
                right = intervals[i][1];
            }
        }
        return count;
    }
}

繼續堅持！

14.劃分字母區間

字串 S 由小寫字母組成，我們要把這個字串劃分為盡可能多的片段，同一字母最多出現在一個片段中，回傳一個表示每個字串片段的長度的串列，

解題思路:
問題分析：
這道題如果按照貪心的做法的話和青蛙跳臺階類似，首先我們可以對每個字母最后出現的位置進行存盤，在遍歷的時候更新已經遍歷過的字母出現的最遠位置，如果到了最遠的位置就說明后面沒有在出現前面的字母了，畫個圖理解一下：

后面同理，不畫了，框框太多畫腦溢血了，遍歷的時候更新findLast字典，里面存盤每個字母最后出現的位置，然后將最后出現的位置設定為第一區見遍歷的最遠位置，后續在遍歷這個區間的時候對這個最遠位置進行更新，如果標針 i 到達了最遠位置，說明前面的字符在后面字符中沒有出現， 化歸這個程序，
問題抽象：
第一次遍歷：更新findLast字典，第二次遍歷：更新當前區間最遠邊界如果滿足標針到達區間終點，將長度加入結果集，
實作步驟：
1、遍歷更新findLast字典，
2、遍歷尋找每個區間的最遠邊界，
3、判斷是否到達了最遠邊界，如果到達最遠邊界，就加入結果集，

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] findLast = new int[26];
        List<Integer> ans = new ArrayList<>();
        // 遍歷更新findLast字典
        for (int i = 0; i < s.length(); i ++) {
            char c = s.charAt(i);
            findLast[c - 'a'] = i;
        }
        // 初始化起點區間
        int left = 0;
        int right = findLast[s.charAt(0) - 'a'];
        // 遍歷更新最遠邊界
        for (int i = 0; i < s.length(); i ++) {
            char c = s.charAt(i);
            // 更新最遠邊界
            right = Math.max(right, findLast[c - 'a']);
            // 到達最遠邊界 加入結果集
            if (i == right) {
                ans.add(right - left + 1);
                // 更新下一個區間的起點
                left = right + 1;
            }
        }
        return ans;
    }
}

特殊解法：

當然這道題我在一開始做的時候想到的方法并不是貪心，而是倒序遍歷的方式，我搜了搜，官方解答以及大家都沒有給出這個解法，大概是自己第一個發現的叭，嘿嘿嘿， 結果耗時和貪心耗時一樣都是5ms，思路就是倒序遍歷，通過hash陣列存盤每個字符的數量，在遍歷的時候判斷，如果遍歷過的區間每個字符的數量都減到0了，就回傳這個長度，
噫？ 突然發現正序好像也能實作 … 好叭，時間復雜度其實是比貪心多的，因為每次要遍歷字串不過還好，最差是O(n2).代碼貼下去了，感興趣自己看一看，沒有用到貪心，給出了詳細的注釋，

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] hash = new int[128];
        // 存盤每個字符的數量
        for (int i = 0; i < s.length(); i ++) {
            char c = s.charAt(i);
            hash[c - '0'] ++;
        }
        // 存在雙端佇列中
        Deque<Integer> ans = new LinkedList<>();
        int count = 0;
        int right = s.length() - 1;
        // 倒敘遍歷
        for (int i = s.length() - 1; i >=0 ; i --) {
            char c = s.charAt(i);
            // 減去字符的數量
            hash[c - '0'] --;
            // 如果滿足區間數量字符的個數都為0
            if (checkAdd(s, hash, i, right)) {
            	// 加入結果集
                ans.offerFirst(right - i + 1);
                right = i - 1;
            }
        }
        return new ArrayList<>(ans);
    }
	// 判斷區間內字串是否不存在hash字典中
    public boolean checkAdd(String s, int[] hash, int left, int right) {
        for (int i = left; i <= right; i ++) {
            char c = s.charAt(i);
            if (hash[c - '0'] > 0) {  
                return false;
            }
        }
        return true;
    }
}

百分之90了，激不激動！

15.單調遞增的數字

給定一個非負整數 N，找出小于或等于 N 的最大的整數，同時這個整數需要滿足其各個位數上的數字是單調遞增，
（當且僅當每個相鄰位數上的數字 x 和 y 滿足 x <= y 時，我們稱這個整數是單調遞增的，）

解題思路:
問題分析：
我們根據正常思路來分析這道題，比如332這個例子來說：我們人眼掃描一下，大概這么分析的想讓它變成單調遞增的最大整數，第一眼就是把332變成329，這是第一步，第二步在變成229，滿足條件的情況下，將中間可以調整的數字（2處在[2,9]中間）盡量的變到范圍內的最大，即9.這樣229就變成了299，滿足單調遞增條件的同時是最大的N，同理分析，遇到其他這種可以將每一位的數字都盡可能的“拉到最大”，是不是只需要將 xy… （其中x > y） 變成x-1 99…9就可以了，這樣又滿足單調遞增，又滿足最大N了，再給大家分析一個較為一般化例子：123321

我們發現在求解這個最終值的時候就是在盡可能的讓后面的數字變成9，這樣子既滿足單調遞增，又滿足最大，那我們如何確定什么時候開始填充9呢？我們明確填充9的目的，并不是盲目填充，比如題目中的樣例1234就很好的符合了單調最大的特點，不需要填充9， 只有遇到了前一位大于后一位產生了非單調遞增的時候，我們進行填充作業，同時將前一位減小一避免超過了原來的值，分析完，我們只需要得知哪里開始不滿足前一位比后一位小，找到了后開始我們的 - 1和填充 9 的作業，問題來了 在遍歷序列的時候，我們該以什么方向遍歷比較好呢？ 為了能夠更好的利用已經修改過的值以及避免重復作業，我們通過舉的例子發現， 從后向前掃描可以在一次掃描內就可以完成替換作業，而不會出現前一位減1后又小于前前1位這樣的尷尬局面，
問題抽象：
第一次遍歷：從后向前遍歷，確定哪里開始不滿足前一位小于后一位，并將不滿足的前一位減小1位，記錄下來該位置，用來后續填充后面位置為9，
第二次遍歷：從記錄下來的位置開始，向后全部填充9，回傳答案，
實作步驟：
1、將數字n轉換成字符陣列，
2、倒敘遍歷陣列，同時修改不滿足條件的值，另前一位-1，并記錄下來不滿足條件的最后位置，
3、從不滿足條件的最后的位置開始，將后面所有位置9，
4、回傳陣列轉換成數字，

class Solution {
    public int monotoneIncreasingDigits(int n) {
    	// 將數字轉換成字符陣列
        char[] num = Integer.toString(n).toCharArray();
        int start = num.length;
        // 倒序遍歷
        for (int i = num.length - 1; i > 0; i --) {
        	// 找到不滿足條件的位置
            if (num[i - 1] > num[i]) {
            	// 更新并記錄不滿足條件的最前面的位置
                start = i;
                // 將前面數字減1
                num[i - 1] --;
            }
        }
        // 將記錄下來最前面不滿足條件位置后面所有的數字置9
        for (int i = start; i < num.length; i ++) {
            num[i] = '9';
        }
        // 轉換成數字回傳
        return Integer.parseInt(new String(num));

    }
}

還有兩道題！！

16.買賣股票的最佳時機含手續費

給定一個整數陣列 prices，其中第 i 個元素代表了第 i 天的股票價格 ；非負整數 fee 代表了交易股票的手續費用，
你可以無限次地完成交易，但是你每筆交易都需要付手續費，如果你已經購買了一個股票，在賣出它之前你就不能再繼續購買股票了，
回傳獲得利潤的最大值，
注意：這里的一筆交易指買入持有并賣出股票的整個程序，每筆交易你只需要為支付一次手續費，

解題思路:
問題分析：
老實說，這道題我剛剛看見的時候也有點懵，這也能貪心的嗎？我自己舉了兩個例子，給大家一起分析一下這道題的思路：
例子一：
[1, 4, 9] fee = 2的情況：1的時候買入4的時候賣出，4的時候買入9的時候賣出， 總profit = 4 - 1 - 2 + 9 - 4 - 2 = 4 而更好的策略是 1買入， 9 賣出 ： 總profit = 9 - 1 - 2 = 6
這個時候我們就要考慮，遇到這個時候我們該怎么辦了？我們換一種思路，我們更新profit = 4 - 1 - 2，并且持有 4 - 2 = 2的股票，這樣遇到9的時候就不會因為多扣除2塊錢的手續費而虧損了，（相當于計算利潤并繼續持有，并沒有完全的賣出）
例子二： [1, 4, 3, 9] fee = 2的情況：
按章上面的思路 1的時候買入，4的時候假裝賣出，更新profit = 4 - 1 - 2 = 1；然后當前持有2 在 3的時候賣掉會虧1塊錢，所以不賣，在9的時候賣 這樣第二波就是 profit += 9 - 2 - 2 ； profit = 6 滿足正確答案，
問題抽象：
確定買入價格，如果股票價格低于買入價格，就更新買入價格為更低的那個，如果遇到賣了能漲價的股票就更新利潤，并持有賣出的便宜了 fee 塊錢的股票，化歸初始狀態，
實作步驟：
1、初始化買入價格，
2、回圈遍歷：遇到比初試價格便宜的就更新買入價格，
3、遇到賣了能賺錢的股票就賣出股票，并持有相當于少了 fee 的等額股票，`

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        // 初始化買入價格
        int buy = prices[0];
        int profit = 0;
        for (int i = 1; i < n; i ++) {
        	// 遇到更便宜的股票， 買入
            if (buy > prices[i]) {
                buy = prices[i];
                // 遇到賣了能賺錢的股票
            } else if (buy < prices[i] - fee) {
            	// 賣出， 并計算利潤
                profit += prices[i] - buy - fee;
                // 持有相當于減了手續費的股票
                buy = prices[i] - fee;
            }
        }
        return profit;
    }
}

就剩最后一題了！！

17.監控二叉樹

給定一個二叉樹，我們在樹的節點上安裝攝像頭，
節點上的每個攝影頭都可以監視其父物件、自身及其直接子物件，
計算監控樹的所有節點所需的最小攝像頭數量，


解題思路:
問題分析：
這道題看上去比較復雜，不過我們通過示例可以看出來，要想覆寫所有的，又想是攝像頭最少，肯定是從葉子結點開始考慮是否安插攝像頭了，舉個例子一看就明白了，上圖：

有這么一個例子的話，如果從頭節點開始看，沒有被覆寫到，裝一個攝像頭后，葉子節點都沒有被覆寫到，這樣葉子結點們就得繼續裝攝像頭，如圖：

而我如果從葉子結點開始看，將攝像頭放在葉子結點的上面，這樣我們就可以大大減少了攝像頭的使用：

這時候不管頭節點有沒有被覆寫到，頂多結果就差1，而從上往下看的話，就可能差2的h次方個攝像頭了，因此，這道題的貪心策略是從下往上看的，那么如何遍歷樹才能實作從下往上看呢，不難知道肯定是二叉樹的后續遍歷了，那么如何確定結點是否需要安裝攝像頭呢？/ 這時候我們就得定義回傳值型別，來通過左右孩子的狀態來判斷是否需要安裝攝像頭了，這里我們定義3種狀態來描述所有可能的情況：
第一種：0 -> 表示沒有被覆寫到，
第二種：1 -> 表示被覆寫到了，
第三種：2 -> 表示有攝像頭（和第二種的區別就是兒子和父親都是狀態1），
定義完狀態，我們就可以根據狀態來確定當前結點是否需要安裝攝像頭了，這里有這么幾種情況：
第一種情況： 左右孩子都被覆寫到了，我們就不需要安裝攝像頭了，因為安裝要浪費重疊的部分，我們回傳0，讓這個節點的父親來安裝攝像頭，這樣可以節省，
第二種情況： 左右孩子有沒被覆寫到的，我們就必須安裝攝像頭，確保每個節點必須被覆寫到，
第三種情況： 左右孩子有攝像頭，我們就回傳1，表示這個節點被覆寫到了，
只要明確了貪心策略，狀態集合，遍歷方式，以及回傳值型別，就可以輕松寫出后續遍歷的代碼啦，
問題抽象：
定義后續遍歷函式，確定空節點回傳-1，進行左右遞回，根據左右孩子的型別，進行相應的回傳值，如果需要更新攝像頭數量，就進行更新，
實作步驟：
1、定義后續遍歷函式，
2、確定空節點回傳型別，
3、遞回左孩子與右孩子，
4、對后序遍歷的結果來確定左右孩子的父親是否需要安裝攝像頭，或者回傳1，或者0，
5、遞回這個程序，最后判斷根節點是否需要安裝攝像頭，

class Solution {
    private int count = 0;
    public int minCameraCover(TreeNode root) {
    	// 最后判斷頭節點需不需要安裝攝像頭
        if (postOrderTraverel(root) == 0) count++;
        return count;
    }
    // 回傳值，-1:表示空節點 0:表示無覆寫 1:表示有覆寫 2:表示放置攝像頭
    private int postOrderTraverel(TreeNode root) {
        if (root == null) return -1;
		// 后序遍歷方式
        int left = postOrderTraverel(root.left);
        int right = postOrderTraverel(root.right);
		// 只要有一個沒覆寫到，就要回傳2，并安裝攝像頭	
        if (left == 0 || right == 0) {
            count++;
            return 2;
        }
		// 只要有一個有攝像頭，就回傳1
		// 注意這里不包括一個孩子沒覆寫的情況，在上面已經優先回傳了
        if (left == 2 || right == 2) {
            return 1;
        }
		// 0表示沒有覆寫到，葉子節點也屬于0
        return 0;
    }
}

恭喜你！你已經無可匹敵了！

噫？為什么少了3分？
當然是剩下的一鍵三連啦！！

辛苦肝了這么久點個三連叭～

恭喜你三連成功～

關注我，及時看到最新的演算法題集詳細歸納整合講解！
讓我們一起進步吧～

下一期：動態規劃很難嗎？大廠面試總是問？從此不再怕dp！