貪心，顧名思義就是越貪越好，越多越有易，他給我的感覺是，通常是求最大或最小問題，相比于動態規劃貪心讓人更加琢磨不透，不易看出方法，為此在這記錄我所見過的題型和思維方法，以便回頭看看…

核心思想:動態規劃是借用之前所有的最佳狀態，來推理出當前的最佳狀態，與眾不同，貪心則是不需要之前的狀態，根據一個價值標準’拿的越多越好’,然而這種價值標準必定沒有影響后效性，比如來到某個狀態點時，消耗了較高代價拿到了最大效益，雖然對于當前狀態來說，但是對于未來的某個·點來說，也許有更加好的選擇消耗更少的代價來獲取較高的效益，所以通常貪心的目的是，找到一種標準價值，按照標準價值來越多越好，或者是通過一定單調性排序，確保每一步都是最優解，然而這一步通常是最難的。

632. 最小區間

你有 k 個 非遞減排列 的整數列表。找到一個 最小 區間，使得 k 個列表中的每個列表至少有一個數包含在其中。
我們定義如果 b-a < d-c 或者在 b-a == d-c 時 a < c，則區間 [a,b] 比 [c,d] 小。

示例 1：
輸入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
輸出：[20,24]
解釋：
列表 1：[4, 10, 15, 24, 26]，24 在區間 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在區間 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在區間 [20,24] 中。

這是一道困難題，確實不好想,他的解題思路是，一直觀察每個數組的最小值，對于這幾個值來說，當前幾個數的值顯然是最小的那個數的最佳狀態，不好解釋為什么，憑想吧。于是可以將這個數的價值記錄并彈出，依次循環，再找出最佳結果。

135.分發糖果

n 個孩子站成一排。給你一個整數數組 ratings 表示每個孩子的評分。
你需要按照以下要求，給這些孩子分發糖果：
每個孩子至少分配到 1 個糖果。
相鄰兩個孩子評分更高的孩子會獲得更多的糖果。
請你給每個孩子分發糖果，計算并返回需要準備的最少糖果數目 。

記得第一次作這題時，確實被這種思維感到震驚，后來發現這種思維其他題也會用到，因此是一個不錯的例題。

盡量少的分發糖果，我們先將每個人分發一個糖果，正向遍歷，如果后一個人的分數大于前一個人，那么后者在前者的基礎上加1(確保右邊人分數大時，右邊人的糖果合理大于左邊)，再次逆向遍歷，左邊大于右邊人分數時，左邊人糖果為右邊人糖果加1（確保左邊人糖果的合理性);

這種兩次遍歷的思維，將在下一題同樣遇到。
581. 最短無序連續子數組

給你一個整數數組 nums ，你需要找出一個 連續子數組 ，如果對這個子數組進行升序排序，那么整個數組都會變為升序排序。
請你找出符合題意的 最短 子數組，并輸出它的長度。

這題同樣是利用左右兩次遍歷，有上一題的思維。

要想找到不合理的區間，我們只需要找到最右邊的不合理數，以及最左邊不合理的數，那么什么叫做不和理呢？顯然是左邊的數大于右邊或者右邊的數大于左邊的數，如果一個數的左邊沒有比他大的數，右邊同樣沒有比他小的數，那么說明該數是一個合理的數，我們可以先正向遍歷，篩選出左邊比自己大的不合理的數，然后再逆向遍歷篩選出右邊小于自己的數，挑出最左邊和最右邊下標就可以了。

這題與上一題唯一不一樣的是，上一題是構造合理環境，這一題是檢查不合理環境。

根據規律判斷貪心

分成K份的最大乘積

問題：一個數字n一定分成k份，得到的乘積盡量大是多少，數字n和k可能很大，結果需對100000007取模。

這題第一眼想到的是暴力遞歸，但是即使是記憶化搜索，對于較大數字，也難免會超時，我們先嘗試前幾個數字最大解，觀察一下結果
n=4 2 * 2
n=5 3 * 2
n=6 3 * 3
n=7 2 * 2
n=8 3 * 3 * 2
n=9 3 * 3 * 3
n=10 3 * 3 * 2 * 2
n=11 3 * 3 *3 * 2
n=12 3 * 3 * 3 * 3
n=13 3 * 3 * 3 * 2 * 2

可以發現，當一個數大于4時，可以拆出3時盡量拆3，這樣使得乘積最大，當然可以用數學極限來證明，但是還是當作例題記錄一下的好。在遇到類似的題也可以考慮一下找規律，雖然這樣的題很少，但是對于沒有思路的數學問題，還是可以使用這樣方法快速找到規律來解題的

排序使問題呈現一定單調性

執行所有任務的最少初始電量
每個任務有兩個參數，需要耗費的電量、至少多少電量才開始這個任務
返回手機需要的初始電量，才能執行完所有的任務

仔細想想，我們不難發現，當需要消耗的電量相同時，那么我們應該先讓至少電量最多的任務先完成，當至少電量相同時，應該讓消耗電量少的先完成。
但是問題來了，如果需要消耗少的與至少電量少組合在一起，或是消耗多和至少多的組合在一起，那么我們應該怎么判定優先級呢。既然這樣的話，我們將至少電量減需要電量作為值，來排序優先級，直觀上感覺是對的，事實上也確實如此，但是關于證明我還沒有想好，有點玄學。
對于有的題，此法是行不通的，我見過類似的題目，但是將兩因素作差值為優先級并不適用于所有題

知識競賽
最近部門要選兩個員工去參加一個需要合作的知識競賽，每個員工均有一個推理能力值 ai,以及一個閱讀能力bi，如果選擇第i個人和第j個人去參加競賽，兩人在推理能力方面的能力為其兩者推理能力的平均值，閱讀能力同理，現在需要最大化他們表現較差一方面的能力，問這個能力值是多少。

這題依舊是排序解決，只不過是按照兩元素差值的絕對值來排序，依次遍歷每一個人，尋找前面的人與這第i號人的組合最大值，排序后巧妙之處在于，每當來到第i號人，都可以快速求出，第i號人與前面的人組合的最有解，那是因為，對于第i號人來說，他與前面任意一個人組合必定是自己能力最小的作為結果，由于絕對值排序的緣故，前面任何一個人都不可能彌補第i號人在弱勢能力上的差距，所以我們只需要記錄前面所經過的兩能力各最大值即可，每次來到第i號人都可以快速求出組合最優解。
從這題我們應該學到的是，當不得不暴力求解時，嘗試尋找一種策略，使得快速找到一種結果對于第i元素來說一定確保其為最優

可以掌控全局變量的最優決策

在01背包里，其關鍵思想就是要或者不要,來到某個狀態時，可以根據前面的所有最佳狀態獲取當前的最佳狀態，當然，這種思維并不只是在動態規劃里可以使用。
871. 最低加油次數

汽車從起點出發駛向目的地，該目的地位于出發位置東面 target 英里處。
沿途有加油站，用數組 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 個加油站位于出發位置東面 positioni 英里處，并且有 fueli 升汽油。
假設汽車油箱的容量是無限的，其中最初有 startFuel 升燃料。它每行駛 1 英里就會用掉 1 升汽油。當汽車到達加油站時，它可能停下來加油，將所有汽油從加油站轉移到汽車中
為了到達目的地，汽車所必要的最低加油次數是多少？如果無法到達目的地，則返回 -1 。
注意：如果汽車到達加油站時剩余燃料為 0，它仍然可以在那里加油。如果汽車到達目的地時剩余燃料為 0，仍然認為它已經到達目的地。

這題，可以使用動態規劃思想解決，那么我們要維護的信息是什么呢，當油不夠時，我們更期望之前在存儲油最多的加油站加油，于是需要維護路過的加油站，對于來到第i個地點來說其最佳狀態為以下兩種情況 第一：油不夠時dp[i]=之前最大加油站的油+當前剩余的油-當前消耗的油，第二：油夠時，dp[i]=dp[i]-當前消耗的油；唯一貪心的點在于選取之前路過的最高存儲油量的加油站。