目錄
前言（什么是貪心）
leetcode 860.檸檬水找零
leetcode 2208.將數組和減半的最少操作次數
leetcode 179.最大數
leetcode 376.擺動序列
leetcode 300.最長遞增子序列
leetcode 334.遞增的三元子序列
leetcode 674.最長連續遞增序列
leetcode 121.買賣股票的最佳時機
leetcode 122.買賣股票的最佳時機Ⅱ
leetcode 1005.K次取反后最大化的數組和
前言（什么是貪心）
這篇博客算是一個新的開端，因為一共有29道貪心將會在這個系列中被講解
由于29道題目對于單篇博客太多了，所以我會將其分為上中下三個章節對其進行講解，每一篇都有接近10篇貪心
而在開始之前，我們需要先講解一下，貪心是什么，以及怎么樣才算是貪
我們貪心其實就是只關注一個局部，從這個局部之中推導出應該怎么貪，并“希望”能夠得到正確的解法
對的，就是希望，因為貪心不一定是正確的
我們就先用一道找零問題來舉例子，
{40， 20， 10， 5， 1}，現在我們有一個數組，代表我們可以找給顧客的錢（買完飲料之后的找錢），假設客人給了48塊錢，要我們用最少的錢的張數給客人找錢，那我們貪心的算法就應該是能用大額紙幣就用大的，所以我們要貪心的話，就應該先用40塊，然后發現還剩下8塊，就是5+1+1+1這樣子找錢
但如果現在數組是{40， 20， 16， 10， 5， 1}，我們在數組中加了一個16，那么貪心的話其實還是40+5+1+1+1，這是貪心，但是我們會發現16+16+16只用三張即可，所以證明我們貪錯了
這就是我為什么說是“希望”能找到正確的答案
可能看到這里你會覺得，貪心有點像賭狗算法，但其實不然，因為正確的貪心是可以通過證明得出，這樣子的貪心是絕對沒有問題的，注意，是證明，嚴格的數學證明
比如我們為什么第一種情況可以，那是因為40后面是20，40代表兩張20，我如果不用40，我就需要20+20，但這樣子還不如一張40，后面的情況也是如此，所以我們這種貪心才是對的
但是第二種為什么是錯的，因為并不對等，我這里的16是40無法取代的，所以才出現了問題
綜上，貪心是一種關注局部的方法，可以通過證明來保證這樣子貪是對的
還有一點需要大家注意的是，貪心想不出來是正常的！！！
就像田忌賽馬，這也是貪心的一種，但所有人都能想出來嗎？并不是
所以放平心態，學貪心就是學學別人是怎么貪的，積攢經驗，下次再見到的時候就會了
（下文中的標題都是leedcode對應題目的鏈接）
leetcode 860.檸檬水找零
這道題目的解釋在前言中被用做例子，這里就不再解釋了
主要邏輯就是，優先選最大的數額找錢，還有就是，如果我們一剛開始是沒有錢的，所以如果第一個元素不是 5 的話那就直接返回 false，接著如果我們在后面的找錢工作中有10塊或者5塊不夠的情況的話，我們就返回false
另外，我們在收到 20 元的時候需要先判斷一下，我們是否有一張 5 塊和一張 10 塊，有的話就用，沒有的話就判斷一下是否有 3 張 5 塊，還沒有就返回false，有的話就繼續
代碼如下：
class Solution {
public:bool lemonadeChange(vector<int>& bills) {if(bills[0] != 5) return false;int five = 0, ten = 0, twen = 0; for(auto e : bills){if(e == 5) five++;else if( e == 10){if(!five) return false;five--, ten++;}else{if(ten && five) ten--, five--, twen++;else if(five < 3)return false;else five -= 3, twen++;}}return true;}
};leetcode 2208.將數組和減半的最少操作次數
這道題目我們的貪法就是，一直找最大的那個數，然后對其進行減半操作，每進行一次減半操作，我們就將記錄減半次數的計數器++，當我們減少的數減少到數組總和的一半的時候，我們就跳出循環，然后返回計數器即可
首先，為什么我們這一道題目可以這么貪，假設我們第一個數不將最大的數減半的話，那么我們將其他任何一個數減半都沒有這個數減的多（這就是體現了貪心的點，同時也是證明），所以我們這種做法一定是對的
我們每一次都減少當時最大數的一半，如果有其他做法的話，那么減半的必然不是最大的那個數，那么也必然沒有這個數減的多
綜上，我們可以創建一個大根堆，每次都將堆頂的元素取出來進行減半，當減到總和一半的時候，就退出
代碼如下：
class Solution {
public:int halveArray(vector<int>& nums) {priority_queue<double> heap;//默認大根堆double sum = 0;for(auto e : nums) heap.push(e), sum+=e;double n = sum; int in = 0; sum /= 2;while(n > sum){double a = heap.top();heap.pop();n -= a/2;heap.push(a/2);in++;}return in;}
};leetcode 179.最大數
這道題目算不上難，由于我們是將數字以字符串的形式拼接起來，所以我們就應該先對其排個序，以字符串的形式，我們直接取數字 a（假如有 30 和 8，那么字符串下的 8 是比 30 要大的，正好符合我們的要求），和數字 b，進行一個比較，看看是 a+b 的形式大一點還是 b+a 的形式大一點，因為 30 是比 3 要大的，如果直接拼接，那么303是沒有330大的，所以我們需要比較
以這種方式排完序之后，直接從大到小拼接即可
這里我們可以用一個大根堆，比較前就將元素變成string類型，不用在比較的時候每一個都用上to_string，這樣會塊很多
當然你如果不喜歡用堆，那么直接堆原數組進行sort也可以，而博主我待會兒會將兩種方法都放在下面，而我在排序的時候都是用的lambda表達式作為判斷條件，這點看不懂的可以去deepseek一下
代碼如下：
（一，使用堆的版本）
class Solution {
public:string largestNumber(vector<int>& nums) {auto cmp_max = [](string& a, string& b){return a+b < b+a;};priority_queue<string, vector<string> ,decltype(cmp_max)> heap(cmp_max);for(auto e : nums) heap.push(to_string(e));if(heap.top() == "0") return "0";string res;while(!heap.empty()){res += heap.top();heap.pop();}return res;}
};（二，在原數組上直接sort的版本）
class Solution {
public:string largestNumber(vector<int>& nums) {sort(nums.begin(), nums.end(), [](int& a, int& b){return to_string(a)+to_string(b) > to_string(b)+to_string(a);});if(nums[0] == 0)return "0";string res;for(auto e : nums) res += to_string(e);return res;}
};leetcode 376.擺動序列
這道題的貪心策略是要畫圖才能看出來的
我們看這張圖，我們貪心的點就在于，我們可以直接找到每一個波峰和波谷，那就是我們擺動序列最長子序列的情況
試想一下，我們不選波峰的話，那么前面或者后面的數都沒有波峰大，那么假如下一個波谷比我們選的數還要大的話，那么我們找到的長度就一定沒有最優的情況要長
比如 5、16、30、20、27，其中 30 是波谷，假如我們不選30，選了 16，那么20對他來說就是升的情況后面的 27 就還是升，那么我們就會比最優情況長度要少
這其實就已經變相證明了這種貪心的可行性了，因為只有波峰波谷的情況是最優的，其他情況都沒有這種的長度長或者最多和這種情況相等
另外還有一種情況就是相等的情況，這種，我們碰到相等的時候就跳過，判斷就是判斷下一個元素是否和當前元素相等，這樣判斷的原因是，我們在最后一個相等元素時，是不會被看作相等的，因為后面的數和他并不相等，而前面相等的數我們已經continue了，相當于只取了相等元素中的其中一個參與比較
代碼如下：
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();if(n < 2) return n;int left = 0, right = 0, count = 0;for(int i = 0; i < n-1; i++){right = nums[i+1] - nums[i];if(!right) continue;if(left * right <= 0) count++;left = right;}return count+1;}
};leetcode 300.最長遞增子序列
如果你想要學會這道題目的貪心策略的話，那么你需要先把dp版本的給學會先，因為這道題目的貪心策略就是根據dp推出來的（dp就是動態規劃），另外，還需要學會二分查找，不然的話時間復雜度和dp是一樣的都是O(n^2)，用了二分查找之后就是O(logN * N)
首先回顧一下dp版本，我們狀態表示是以 i 位置為結尾，我們前面所有位置中最最長的遞歸子序列的長度是多少
也就是說，我們只關注那個遞增子序列的最后一個元素，這個是關鍵，如果比這個最后一個元素大，那么我們就可以將這個元素接到后面，這個遞增子序列的長度也就可以+1
所以我們可以創建一個數組，里面的每一個元素都代表以這個元素為結尾的遞增子序列
然后，我們假設元素一和二分別是 7、2、6
那么我們先將 7 放入數組中，然后體現我們貪心的地方來了，我們選到 2 的時候，可以跟在 7?后面的元素，一定可以跟在 2 后面，所以我們就將 7 替換成 2
接著是 6，我們發現 6 是可以接在 2 后面的，所以我們就直接將 6 放在數組的第二個位置
可能有人看到這里還是不明白，我就總結一下，首先，這個貪心最終得出來的長度肯定是對的，但是里面的每一個元素大概率不是我們最優情況的元素
這是因為，我們見到小的就更新，大的就往后走的本質是，能接在情況A的數字，一定能接在情況B后面，這是一個一直在更新的，假如我數組中放的是 2、7、16，這代表的是三個不同的序列的結尾，16代表的是前面所有情況中長度為 3 的遞增子序列的結尾位置的值，假設我先來來了一個數字 10 要來代替他，這就說明前面有情況（假設是2、7、10）這種情況和 2、7、16 的長度一樣，都是 3，但是假如我下一個數字是 13 的話，接在 10 的后面能變成長度為 4 的情況，但是卻不能接在 16 后面，前面兩個元素（2、7）一直在更新代表的是后面的有長度也為 1 或者 2 的更優的情況，所以代表的是后面的序列
所以如果數組中后面的元素更新了的話，代表遍歷到后面的時候，有更優但是長度相同的情況能代替這種情況
所以，還是那句話，dp中的是只關注最后一個元素的，我們這里也是一樣，只用關注最后一個元素即可
最后，是我們二分查找算法的帶入
我們將元素放入新開辟的數組中的時候，如果元素很多的話，那么我們還需要對這個數組遍歷一遍，那其實就是 O(N^2) 的時間復雜度，但是這里面的數字是嚴格遞增的，所以我們可以使用二分查找，在 O(logN * N) 的時間復雜度內解決這道題目
代碼如下：
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> arr;arr.push_back(nums[0]);for(int i = 1; i < nums.size(); i++){if(nums[i] > arr.back())arr.push_back(nums[i]);else{int left = 0, right = arr.size()-1;while(left < right){int mid = (left + right) >> 1;if(arr[mid] < nums[i]) left = mid + 1;else right = mid; }arr[left] = nums[i];}} return arr.size();}
};leetcode 334.遞增的三元子序列
這道題目不解釋，就是上一道題目的簡化版本，甚至都不需要新開辟數組和二分查找，只需要兩個變量，如果有可以接在第二個變量后面的情況，就代表有三個元素的情況，那么直接return true 即可
代碼如下：
class Solution {
public:bool increasingTriplet(vector<int>& nums) {int a = nums[0], b = INT_MAX;for(int i = 1; i < nums.size(); i++){if(nums[i] > b) return true;else if(nums[i] <= a) a = nums[i];else b = nums[i];}return false;}
};leetcode 674.最長連續遞增序列
對于這道題目，我們只需要知道一個點，就是，我現在有一個數，他比前面一個數要大，那么我就可以接在他后面，長度就應該是當前的最長長度
但是如果這個數，比前面的數要小，因為是連續的，這就意味著他只能從 1?開始（自身長度為 1），作為一個新的起點開始計數
可以想象一下，就相當于這個數組被分成了一個一個的小部分，互不相交，我們只需要找出這里面的最長的長度即可
代碼如下：
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {int ret = INT_MIN;int count = 1;for(int i = 1; i < nums.size(); i++){if(nums[i] > nums[i-1]) count++;else{ret = max(ret, count);count = 1;}} ret = max(ret, count);return ret;}
};leetcode 121.買賣股票的最佳時機
當我們往后遍歷的時候，我們已經知道前面所有元素中最小的元素是哪個了（定義一個變量，找到一個元素就比較一下就能找到前面所有元素中最小的那一個）
然后我們只需用? ? 當前元素 - 最小值，得出來一個利潤，找到最大利潤即可
這題這樣做是因為，我們只有一次交易機會
或者我們可以換一個思路，當我們將股票數據以折線圖的形式畫出來的時候，我們是能看到最低的波峰和最高的波谷的，將這兩個對于位置的數字相減之后得到的就是結果，因為沒有其他可能會比這個結果要大了
代碼如下：
class Solution {
public:int maxProfit(vector<int>& prices) {int min_val = prices[0], ret = INT_MIN;if(prices.size() == 1) return 0;for(int i = 1; i < prices.size(); i++){ret = max(prices[i] - min_val, ret);min_val = min(prices[i], min_val);} return ret < 0 ? 0 : ret;}
};leetcode 122.買賣股票的最佳時機Ⅱ
我們所有的股票問題其實都能用dp來做，但不一定都可以用貪心，只不過貪心的情況代碼會更好寫，思路會更清晰，關鍵是，時間復雜度也會更低
這一題的關鍵詞是，我們有無數次交易的機會，我們要的是最大的利潤
那換一個角度想，我們要最大利潤，那么我們是不是只要有利可圖，我就直接交易
畫成折線圖就是：
我們圖中的每一個上升的地方，都代表著利潤，那么我們要利潤最大，那就將這些利潤全部加起來即可，這就是最大利潤的情況了
然后如果是相等的情況，我們判不判斷都無所謂，因為不判斷，也就是加上一個利潤為 0 的情況而已，并無變化，但是博主我還是判斷了，也算是強迫癥吧......
代碼如下：
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();if(n == 0 || n == 1) return 0;int left = prices[0], right = INT_MAX;int ret = 0;for(int i = 1; i < n-1; i++){right = prices[i];if(prices[i] == prices[i+1]) continue;else if(prices[i] > left && prices[i] > prices[i+1]){ret += (right - left);left = right;}else if(prices[i] < left && prices[i] < prices[i+1])left = right;} if(left < prices[n-1]) ret += prices[n-1] - left;return ret;}
};leetcode 1005.K次取反后最大化的數組和
這道題目其實沒什么好講的，因為我們的貪法就是一直對最小的那個數進行操作（前提是這個數為負數）
所以我們可以先對這個數組進行一個排序，默認的升序即可
然后在最前面的數字都是最小的數字，我們只需要判斷，這個數字是否是負數，如果是的話就將這個數轉換成整數，并且 k--，而如果 k 已經減小到 0 了或者這個數組里面已經沒有負數了，我們就需要退出了
出來之后我們還需要進行一次排序，因為我們有可能會這樣：
-5、-3、0、2、5? ? ? ? ? k=1
5、-3、0、2、5? ? ? ? ? ?k=0
我們會發現有負數就在中間，再次排序其實就是更新一下數組而已
然后我們就需要判斷了，如果 k 還有的話，那就意味著數組里面必然沒有負數了，因為有負數的話會 k-- 然后轉化為正數，所以我們就可以再進行一次分類討論，也就是 k 是奇數還是偶數
如果是奇數，那么前面所有的偶數次我們都可以對同一個元素使用，最后一次我們只能對最小的那個元素使用，所以就是所有元素相加之后減去兩個第一個元素（當然你也可以在相加的時候不加第一個元素，然后減的時候只減一次即可）
然后是 k 為偶的情況，我們直接數組內全部相加即可
接著如果 k 已經沒了，也是只需要將數組里面所有元素相加即可
代碼如下：
class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int n = nums.size();sort(nums.begin(), nums.end());for(int i = 0; i < n; i++){if(k == 0 || nums[i] >= 0) break;if(nums[i] < 0) nums[i] = -1 * nums[i], k--;} int sum = 0, flag = 0;sort(nums.begin(), nums.end());for(auto e : nums) {sum += e;if(e == 0) flag = 1;}if(k == 0) return sum;else{if(k % 2 == 1 && flag == 0) return sum -= 2*nums[0];else return sum;}return 0;}
};今天這篇博客到這里就結束啦~(￣▽￣)~*
如果覺得對你有幫助的話，希望可以關注一下喔
另外，博主還會盡快更新中和下，屆時會將鏈接放到這篇文章之中，覺得講得好的也可以關注一下喔
最后，如果你有什么疑問，可以直接私信我或者在評論區留言，博主看到了的話一定會為你答疑的
