點(diǎn)贊👍👍收藏🌟🌟關(guān)注💖💖
你的支持是對(duì)我最大的鼓勵(lì)，我們一起努力吧!😃😃

1.買賣股票的最佳時(shí)機(jī)

題目鏈接： 121. 買賣股票的最佳時(shí)機(jī)

題目分析：

買賣股票的最佳時(shí)機(jī)既可以用貪心也可以用動(dòng)規(guī)，其中所有的股票問題都可以只用動(dòng)規(guī)來解，但是有些題用貪心來解思路和寫法是更優(yōu)的。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個(gè)不同的日子 賣出該股票。這句話的意思是買賣股票只能執(zhí)行一次。返回你可以從這筆交易中獲取的最大利潤(rùn)。如果你不能獲取任何利潤(rùn)，返回 0 。

算法原理：

我們用圓圈代表數(shù)組中一個(gè)個(gè)元素。

如果我們把題意搞清楚，我們很容易想到一個(gè)暴力策略，我們要最大利潤(rùn)的話，無非就是在數(shù)組中挑出兩個(gè)位置，一個(gè)位置是買入，一個(gè)位置是賣出，使這兩個(gè)位置的值的差是最大的。此時(shí)我們有一個(gè)暴力解法可以把所有的二元組枚舉出來，也就是兩次for循環(huán)，第一層for依次從左往右固定一個(gè)賣出位置，第二層for依次枚舉買入位置，每到一個(gè)位置就用賣出位置 - 買入位置，把所有情況的差求一個(gè)最大值。當(dāng)固定完一個(gè)賣出位置之后，賣入位置往后走一步，然后買入位置繼續(xù)從頭開始枚舉。

解法一：暴力解法，兩層 for 循環(huán)的暴力枚舉

但是時(shí)間復(fù)雜度是O(N^2)

有了這兩層 for 循環(huán)的暴力枚舉，我們可以想到一個(gè)優(yōu)化方式，固定賣出位置的時(shí)候，我們想找到這一段的最大利潤(rùn)，我們之前是從頭開始枚舉。我們買入點(diǎn)其實(shí)就是在找以該賣出點(diǎn)位置的最大利潤(rùn)，此時(shí)貪心就來了，我們其實(shí)進(jìn)行找到賣入位置之前買入的最小值就行了，然后拿賣出減去前面買入的最小值，就是這個(gè)點(diǎn)賣出的最大利潤(rùn)。所以我們僅需知道賣出之前所有買入位置的最小值就可以了。

我們求最小值如果從前往后遍歷，時(shí)間復(fù)雜度是O(N)，如果固定完一個(gè)賣出位置就已經(jīng)知道前面買入位置的最小值，時(shí)間復(fù)雜度就是O(1)，那整體時(shí)間復(fù)雜度就是O(N)

當(dāng)我們把這個(gè)賣出位置的最大利潤(rùn)知道之后，接下來要求下一個(gè)賣出位置的最大利潤(rùn)，我們可以在去下一個(gè)賣出位置之前，拿之前的 prevMin 和 該賣出位置 做比較 求一個(gè)最小值，就知道 下一個(gè)賣出位置之前所有買入位置的最小值。

解法二： 貪心 + 一個(gè)變量標(biāo)記 “前綴最小值”
時(shí)間復(fù)雜度O(N)

我們這個(gè)貪心策略其實(shí)適合暴力解法結(jié)果是一樣的依舊把所有情況都枚舉到，所以暴力是對(duì)的，貪心也是對(duì)的。

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int ret = 0, prevmin = INT_MAX;for(int i = 0; i < n; ++i){ret = max(ret, prices[i] - prevmin);// 先更新結(jié)果prevmin = min(prevmin, prices[i]); // 在更新最?值}return ret;}
};

動(dòng)態(tài)規(guī)劃：

因?yàn)檫@個(gè)動(dòng)態(tài)規(guī)劃思想其實(shí)就和上面貪心幾乎是一模一樣的，都是找前 i 天 的最低價(jià)格，所以我們直接給代碼。

class Solution {
public:int maxProfit(vector<int>& prices) {// int n = prices.size();// int ret = 0, prevmin = INT_MAX;// for(int i = 0; i < n; ++i)// {//     ret = max(ret, prices[i] - prevmin);// 先更新結(jié)果//     prevmin = min(prevmin, prices[i]); // 在更新最?值// }// return ret;// 動(dòng)態(tài)規(guī)劃//dp[i] 表示: 前 i 天 價(jià)格最低點(diǎn)int n = prices.size(), ret = 0;vector<int> dp(n + 1);dp[0] = INT_MAX;for(int i = 1; i <= n; ++i){ret = max(ret, prices[i - 1] - dp[i - 1]);dp[i] = min(dp[i - 1], prices[i - 1]);}return ret;}
};

2.買賣股票的最佳時(shí)機(jī) II

題目鏈接： 122. 買賣股票的最佳時(shí)機(jī) II

題目分析：

在每一天，你可以決定是否購(gòu)買和/或出售股票，這句話的意思就決定了買賣股票是沒有限制的。你在任何時(shí)候 最多 只能持有 一股 股票。這句話的意思是這一天你手里有股票是不能夠在買的。要想這一天把股票買走，你必須把手里股票賣出之后才能在買。你也可以先購(gòu)買，然后在 同一天 出售，這句話的意思是你可以今天買今天就賣，我們是可以進(jìn)行這樣操作的。

返回 你能獲得的 最大 利潤(rùn) 。

算法原理：

我們把數(shù)組中的數(shù)放在一個(gè)二維平面，能夠很清楚看見股票的增減關(guān)系，還能得到我們的策略。

這道題我們是可以執(zhí)行任意多筆交易，也就是可以選任意點(diǎn)買入股票，任意點(diǎn)賣出股票。此時(shí)我們要獲得最大利潤(rùn)，看這個(gè)圖是否有這樣的想法，你會(huì)選擇在下降趨勢(shì)買賣股票嗎？肯定不會(huì)的。只要是下降趨勢(shì)我們都不會(huì)買賣股票。

所以說我們的貪心策略非常簡(jiǎn)單，在這個(gè)圖像中只要是股票價(jià)格是上升趨勢(shì)的我就買和賣，在上升最低點(diǎn)買入，在上升最高點(diǎn)賣出。那么我就可以獲得最大利潤(rùn)。

水平和下降我們都不會(huì)買賣股票。

貪心策略：只要能獲得正收益，我就交易。

如何實(shí)現(xiàn)？實(shí)現(xiàn)方式有兩種：

1. 雙指針

我們要在數(shù)組中找增加的區(qū)域，所以我們可以先定義一個(gè)指針 i 指向初始位置，同時(shí)定義一個(gè)指針 j ，從指針 i 位置開始往后遍歷，只要當(dāng)前位置的值小于后面位置的值，j 就往后走。如果發(fā)現(xiàn)后面的值小于或者等于 j 位置的值，說明 i 到 j 增長(zhǎng)的區(qū)域已經(jīng)被找到，此時(shí)搞一個(gè)全局的ret，ret += p[j] - p[i]，當(dāng)計(jì)算完這一段的時(shí)候，更新 i 到 j 位置 或者 j + 1位置，然后 j 進(jìn)行從 i 位置開始。如果發(fā)現(xiàn)后面的值比 j 小，沒關(guān)系，j 是不移動(dòng)的，此時(shí)ret += p[j] - p[i] 是等于 0 的。

2. 拆分交易，把一段交易拆分成一天一天

我們求前面這段上升區(qū)域在雙指針哪里其實(shí)是 p[3] - p[1]，此時(shí)我們發(fā)現(xiàn)求這一整段的利潤(rùn)時(shí)，可以拆分成兩段利潤(rùn)。我們會(huì)發(fā)現(xiàn) p[3] - p[1] 正好等于 p[3] - p[2] + p[2] - p[1] 然后p[2]一抵消，兩邊就是相等的。左邊是整體計(jì)算，右邊是分開計(jì)算，它們的利潤(rùn)是一樣的。所以只要是一段上升區(qū)域我們都可以拆分成一天一天。

class Solution {
public:int maxProfit(vector<int>& prices) {// 實(shí)現(xiàn)方式一: 雙指針// int ret = 0, n = prices.size();// for(int i = 0; i < n; )// {//     int j = i;//     while(j + 1 < n && prices[j] < prices[j + 1]) ++j;//找上升的末端//     ret += prices[j] - prices[i];//     i = j + 1;// }// return ret;// 實(shí)現(xiàn)?式?: 拆分成?天?天int ret = 0, n = prices.size();for(int i = 0; i < n - 1; ++i){if(prices[i] < prices[i + 1])ret += prices[i + 1] - prices[i];}return ret;}
};

3.K 次取反后最大化的數(shù)組和

題目鏈接： 1005. K 次取反后最大化的數(shù)組和

題目分析：

對(duì)數(shù)組中的數(shù)取k次取反操作，注意可以多次選擇同一個(gè)數(shù)進(jìn)行進(jìn)行取反操作。以這種方式修改數(shù)組后，返回?cái)?shù)組 可能的最大和。

算法原理：

如果想對(duì)數(shù)組執(zhí)行取反操作讓數(shù)組和是最大的，我們下意識(shí)就會(huì)先挑選負(fù)數(shù)變成正數(shù)，而且是挑選最小的那個(gè)負(fù)數(shù)。

然后根據(jù) k 和 數(shù)組中負(fù)數(shù)的個(gè)數(shù)的關(guān)系，我們進(jìn)行分類討論：

設(shè)整個(gè)數(shù)組中負(fù)數(shù)的個(gè)數(shù)是 m 個(gè)。

1. m > k

負(fù)數(shù)的個(gè)數(shù)比取反k次要多

2. m == k

負(fù)數(shù)個(gè)數(shù)和k的個(gè)數(shù)一樣，其實(shí)可以歸類到第一類情況，直接把所有負(fù)數(shù)轉(zhuǎn)化為整數(shù)。

3. m < k

負(fù)數(shù)個(gè)數(shù)小于k的個(gè)數(shù)

此時(shí)在對(duì) k - m 的奇偶性分析。如果整個(gè)數(shù)組是正數(shù)的話，我們非常不希望把里面的數(shù)變成負(fù)數(shù)。

當(dāng) k - m 是偶數(shù)的時(shí)候，那我們就瘋狂的對(duì)一個(gè)數(shù)進(jìn)行取反操作，對(duì)一個(gè)數(shù)進(jìn)行偶數(shù)次取反操作這個(gè)數(shù)是不變的。

當(dāng) k - m 是奇數(shù)的時(shí)候，我們必須會(huì)讓一個(gè)數(shù)變成負(fù)數(shù)，此時(shí)我們會(huì)讓數(shù)組中最小的數(shù)變成負(fù)數(shù)。損失是最小的。

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int m = 0, minElem = INT_MAX, n = nums.size();for(auto x : nums){if(x < 0) ++m;minElem = min(minElem, abs(x));// 求絕對(duì)值最?的那個(gè)數(shù)}// 分類討論int ret = 0;if(m > k){sort(nums.begin(), nums.end());for(int i = 0; i < k; ++i)// 前 k ?個(gè)負(fù)數(shù)，變成正數(shù)ret += abs(nums[i]);for(int i = k; i < n; ++i)// 后?的數(shù)不變ret += nums[i];}else{// 把所有的負(fù)數(shù)變成正數(shù)for(auto x : nums) ret += abs(x);if((k - m) % 2)// 判斷是否處理最?的正數(shù){ret -= minElem * 2;}}return ret;}
};

4.按身高排序

題目鏈接： 2418. 按身高排序

題目分析：

這道題并不是一道貪心題，它只是一道排序題。但是這道題里面的排序思想會(huì)用到下到題里面。

給你一個(gè)字符串?dāng)?shù)組 names ，和一個(gè)由 互不相同 的正整數(shù)組成的數(shù)組 heights 。兩個(gè)數(shù)組的長(zhǎng)度均為 n 。對(duì)于每個(gè)下標(biāo) i，names[i] 和 heights[i] 表示第 i 個(gè)人的名字和身高，也就是說這兩個(gè)數(shù)組是綁定的。按身高 降序 順序返回對(duì)應(yīng)的名字?jǐn)?shù)組 names。

算法原理：

這道題主要就是排序，接下來我們就想如何排序就可以了。

我們要對(duì)身高進(jìn)行降序排序，但是不能直接排，如果不管名字直接拿升高排序，排完序之后身高和姓名就可能不是對(duì)應(yīng)的了。 我們必須要保證排完序后姓名和升高映射關(guān)系要能對(duì)應(yīng)上。

此時(shí)我們有三種解決方式：

解法一：創(chuàng)建二元組

1. 創(chuàng)建一個(gè)新的數(shù)組pair<int，string>，把原始身高和姓名綁定重新放在pair數(shù)組里面
2. 對(duì)新的數(shù)組按照第一個(gè)元素排序
3. 按照順序把名字提取出來即可

解法二： 利用哈希表存下映射關(guān)系

1. 先用哈希表存下映射關(guān)系 <身高，名字>
2. 對(duì)身高數(shù)組排序
3. 根據(jù)排序后的結(jié)果，往哈希表里找名字即可

雖然這兩種方法都能解決問題，但是都是有缺陷的。統(tǒng)一的缺陷就是既要存身高也要存名字，第二個(gè)缺陷就是解法二的缺陷，有可能身高時(shí)重復(fù)的，但是我們的hash里key是不能相同的，此時(shí)解決方法就是把string改成string數(shù)組。

解法三：對(duì)下標(biāo)排序（非常常用的一個(gè)技巧）

在排序的時(shí)候，雖然想排序但是并不想改變?cè)卦嫉奈恢谩Ｒ簿褪钦f排序之前元素在那個(gè)位置排序后該元素還在那個(gè)位置。剛好我們這道題就符合這樣排序，排序后身高和姓名還是和之前一一對(duì)應(yīng)。

1. 創(chuàng)建一個(gè)下標(biāo)數(shù)組
2. 僅需對(duì)下標(biāo)數(shù)組排序
3. 根據(jù)下標(biāo)數(shù)組排序后的結(jié)果，找到原數(shù)組的信息

假如有下面的姓名數(shù)組和身高數(shù)組，我們的策略就是創(chuàng)建一個(gè)下標(biāo)數(shù)組，下標(biāo)數(shù)組保存對(duì)應(yīng)的信息的下標(biāo)。然后僅需對(duì)下標(biāo)數(shù)組排序，排序的時(shí)候就按照要求來排，這里下標(biāo)數(shù)組排序按照身高的降序來排，所以我們要重寫一個(gè)排序比較方法。排序我們也是也是對(duì)下標(biāo)數(shù)組排序，原始的數(shù)組我們可沒動(dòng)，接下來通過下標(biāo)就可以找到對(duì)應(yīng)的身高和姓名。

class Solution {
public:vector<string> sortPeople(vector<string>& names, vector<int>& heights) {// 解法一 // // 1. 創(chuàng)建一個(gè)pair<int,string>數(shù)組// int n = heights.size();// vector<pair<int,string>> x(n);// for(int i = 0; i < n; ++i)//     x[i] = make_pair(heights[i],names[i]);// // 2. 對(duì)數(shù)組元素進(jìn)行排序// sort(x.begin(), x.end(), [](const pair<int,string>& p1, const pair<int,string>& p2)// {//     return p1.first > p2.first;// });// // 3. 提取結(jié)果// vector<string> ret;// for(auto p : x)// {//     ret.push_back(p.second);// }// return ret;// 解法二// // 1.創(chuàng)建一個(gè)hash表// unordered_map<int,string> hash;// int n = heights.size();// for(int i = 0; i < n; ++i)//     hash[heights[i]] = names[i];// // 2. 對(duì)身高數(shù)組進(jìn)行排序// sort(heights.begin(), heights.end(), greater<int>());// // 3.提取結(jié)果// vector<string> ret;// for(auto x: heights)// {//     ret.push_back(hash[x]);// }// return ret;// 解法三// 1. 創(chuàng)建一個(gè)下標(biāo)數(shù)組int n = heights.size();vector<int> index(n);for(int i = 0; i < n; ++i) index[i] = i;// 2. 對(duì)下標(biāo)進(jìn)行排序sort(index.begin(), index.end(), [heights](const int& i, const int& j){return heights[i] > heights[j];});// 3. 提取結(jié)果vector<string> ret;for(auto i : index){ret.push_back(names[i]);}return ret;}
};

5.優(yōu)勢(shì)洗牌（田忌賽馬）

題目鏈接： 870. 優(yōu)勢(shì)洗牌

題目分析：

給定兩個(gè)長(zhǎng)度相等的數(shù)組 nums1 和 nums2，nums1 相對(duì)于 nums2 的優(yōu)勢(shì)可以用滿足 nums1[i] > nums2[i] 的數(shù)目來描述。也就是說相同位置只要nums1數(shù)組的數(shù)比nums2數(shù)組的數(shù)大就存在一個(gè)優(yōu)勢(shì)。

返回 nums1 的任意排列，使其相對(duì)于 nums2 的優(yōu)勢(shì)最大化。也就是想辦法對(duì)第一個(gè)數(shù)組進(jìn)行排序，使排序后的優(yōu)勢(shì)使最大的。

算法原理：

我們先回憶田忌賽馬的故事，當(dāng)把這道題題意搞清楚后你會(huì)發(fā)現(xiàn)它和田忌賽馬的故事是一模一樣的。田忌賽馬無非就三匹馬在比，我們這里是有很多馬在比。但是它的策略和田忌賽馬的策略是一樣的。我們從田忌賽馬的故事提取最優(yōu)策略。

田忌賽馬故事很簡(jiǎn)單，齊威王和田忌在賽馬，按照等級(jí)把馬劃分為上、中、下三匹馬，它們每次都按照上、中、下的順序比較，但是同級(jí)別下齊威王的馬比田忌的好，所以結(jié)果都每次都是齊威王贏。這個(gè)時(shí)候來了一個(gè)孫臏，它給田忌出了一個(gè)策略，讓田忌更改一下馬的出場(chǎng)順序，改成 下、上、中。此時(shí)田忌在和齊威王比較，雖然他的下等馬對(duì)齊威王的上等馬是慘敗的，但是他的上等馬是勝于齊威王的中等馬，中等馬勝于齊威王的下等馬。此時(shí)田忌獲得勝利。

接下來我們從這個(gè)故事中提取孫臏的最優(yōu)策略，為了方便敘述我們將他倆的馬從小到大排序。剛開始拿著田忌的下等馬去比齊威王的下等馬你會(huì)發(fā)現(xiàn)是干不過的，如果比不過就相當(dāng)于齊威王所有的馬，田忌的下等馬都比不過。因?yàn)槲覀円呀?jīng)按照從小到大排序了，如果田忌的下等馬連齊威王最差的那匹馬都比不過，那它所有的馬都比不過。這里我們的第一個(gè)貪心策略，如果連最差的比不過，那就去拖累掉最強(qiáng)的那匹馬（廢物利用最大化）。接下來考慮田忌的中等馬，發(fā)現(xiàn)中等馬能打過齊威王的下等馬，上等馬也能打過齊威王的下等馬，此時(shí)第二個(gè)貪心策略，當(dāng)前最差的馬就已經(jīng)能比掉齊威王最差的馬，絕對(duì)不會(huì)浪費(fèi)更優(yōu)秀的馬。

總結(jié)一下最優(yōu)策略：

1. 排序
2. 如果比不過，就去拖累掉對(duì)面最強(qiáng)的那一個(gè)
3. 如果能比過，那就直接比

接下來我們模擬一下：

先對(duì)數(shù)組進(jìn)行排序，（我們是要把nums1數(shù)組修改成ret）

8比不過11，我們的策略是廢物利用最大化，直接去匹配最強(qiáng)的32

12比的過11，直接放

24比的過13，直接放

32比的過25，直接放

這個(gè)ret就是我們最優(yōu)的策略，但是這個(gè)結(jié)果和答案給的不一樣！

原因是答案是按照未排序之前的num2的順序來匹配最終結(jié)果的。意思就是如果是11對(duì)12，應(yīng)該是原始的nums2數(shù)組的11的位置放12，而不是在排完序后的第一個(gè)位置放12.

同理其他都是如此，然后這個(gè)數(shù)組才是我們要的最終結(jié)果

原因就在于我們排完序之后是要按照之前排序之前的數(shù)組來還原的，所以就出現(xiàn)了，雖然想排序，但是原來的順序我還要知道。那如何實(shí)現(xiàn)這一點(diǎn)呢？《身高排序》 這到題我們正好用了這個(gè)技巧，又想讓數(shù)組排序，又想找到之前的相對(duì)位置，我們的策略是直接排序下標(biāo)數(shù)組。不排原始數(shù)組，對(duì)下標(biāo)數(shù)組進(jìn)行排序，然后通過下標(biāo)數(shù)組找到原始的數(shù)，最終就能把ret對(duì)應(yīng)到原始的位置。

接下來我們?cè)谀M一下這個(gè)過程。

先對(duì)下標(biāo)數(shù)組排序，如何排序之前已經(jīng)說過改變排序規(guī)則，這里我們還需要兩個(gè)指針，left指向num2下標(biāo)數(shù)組排序后的第一個(gè)元素的下標(biāo)，right指向nums2下標(biāo)數(shù)組排序后的最后一個(gè)元素的下標(biāo)。

依次遍歷nums1，每次和left所指向的下標(biāo)對(duì)應(yīng)nums2中的元素做比較nums2[index2[left]]，

8比不過11，把8放在最后一個(gè)位置，此時(shí)并不是把8放在ret最后一個(gè)位置，而是把8放在nums2排完序之后的最后一個(gè)位置所對(duì)應(yīng)的下標(biāo)的位置。也ret下標(biāo)為2的位置。然后right–，代表之前的數(shù)已經(jīng)匹配過了，此時(shí)最后一個(gè)位置的就是下標(biāo)1。

12比的過left所指向下標(biāo)對(duì)應(yīng)的數(shù)11，就放在第一個(gè)位置，第一個(gè)位置下標(biāo)是3，然后left++

24比的過left所指向下標(biāo)對(duì)應(yīng)的數(shù)13，就放在0位置，然后left++

32比的過left所指向下標(biāo)對(duì)應(yīng)的數(shù)25，放在下標(biāo)1的位置，此時(shí)nums1遍歷完就結(jié)束了。

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();// 1. 排序sort(nums1.begin(), nums1.end());vector<int> index2(n);for(int i = 0; i < n; ++i) index2[i] = i;sort(index2.begin(), index2.end(), [&](const int& i, const int& j){//所有下標(biāo)按照nums2里面升序形式排序return nums2[i] < nums2[j];});// 2. 田忌賽馬vector<int> ret(n);int left = 0, right = n - 1;for(int i = 0; i < n; ++i){if(nums1[i] > nums2[index2[left]]){ret[index2[left]] = nums1[i];++left;}else{ret[index2[right]] = nums1[i];--right;}}return ret;}
};

證明：

證明方法：交換論證法

nums1表示排序后升序的樣子，nums2也表示排序后的樣子，并且nums1表示的貪心解

在來一個(gè)nums1表示最優(yōu)解的情況

交換論證法就是在最優(yōu)解不失去最優(yōu)性的情況下調(diào)整成貪心解的話，那我們就說貪心解就是最優(yōu)解。

從左往右掃描貪心解和最優(yōu)解的匹配情況，當(dāng)遇到第一個(gè)它們倆匹配不同的情況，就考慮這個(gè)點(diǎn)。

我們要分兩種情況討論：

1. 貪心解比的過

貪心解比得過，那就去匹配第一個(gè)，最優(yōu)解和貪心解不一樣，最優(yōu)解就去匹配后面的。然后最優(yōu)解后面的在和第一個(gè)匹配

接下來就看最優(yōu)解調(diào)整成貪心解會(huì)不會(huì)變差。

如何調(diào)整就是調(diào)的和貪心解一樣就可以了，這里我們?cè)O(shè)一些變量，然后在貪心解比得過我們有一個(gè)不等式 b > a > x1

a > x1，b > x1，這兩條線可以抵消

剩下兩條線我們不容易得出勝負(fù)情況， 我們僅知道 b > a > x1，我們并不知道a是否大于x2，也并不知道b是否大于x2。但是我們可以粗略估計(jì)一下用b來比較x2是更優(yōu)的，原因是最優(yōu)解之前拿的是較小的a都能和x2匹配，調(diào)整完之后拿較大的b和x2匹配，所以絕對(duì)是更優(yōu)的。a能勝過x2，b一定能勝過，a打不過x2，但是b比a大是有可能打得過x2的。 所以我們第一種情況是可以的。

2. 貪心解比不過

如果比不過，貪心選擇的策略就是和最后一個(gè)抵消，最優(yōu)解肯定不是最后一個(gè)，接下來我們繼續(xù)調(diào)整。依舊是調(diào)整后的別比之前的差就可以。

我們的談貪心解是比不過第一個(gè)才會(huì)抵消最后一個(gè)，也就是比nums2最小的還要小。調(diào)整之前拿最優(yōu)解的a和nums2前面的匹配，調(diào)整后和nums2最后一個(gè)匹配，反正都不會(huì)得分所以可以抵消。

剩下還有兩條線，你會(huì)發(fā)現(xiàn)調(diào)整最優(yōu)解b之后是更優(yōu)的，b是固定的，之前b是去匹配較大的的x2，現(xiàn)在是匹配較小的x1，b能打過x1一定能打過x2，b打不過x2可能會(huì)打過x1。

因?yàn)槲覀冏顑?yōu)解調(diào)整后是更優(yōu)的，所以最優(yōu)解肯定能在不失去最優(yōu)性的前提下調(diào)整到貪心解。