一、LeetCode 738.單調(diào)遞增的數(shù)字

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html

狀態(tài)：已解決

1.思路?

?????????如何求得小于等于N的最大單調(diào)遞增的整數(shù)？98，一旦出現(xiàn)strNum[i - 1] > strNum[i]的情況（非單調(diào)遞增），首先想讓strNum[i - 1]--，然后strNum[i]給為9，這樣這個(gè)整數(shù)就是89，即小于98的最大的單調(diào)遞增整數(shù)。也就是說，我們只需要找到最先不滿足單增性質(zhì)的位置，然后將前一個(gè)元素-1，后面的所有元素變?yōu)?即可。因此，代碼分兩步：

（1）找到整數(shù)中最先不滿足單增性質(zhì)的前后元素：

? ? ? ? 遍歷數(shù)組，比較前后兩個(gè)元素的大小，然后不斷維護(hù)前者大于后者的最新下標(biāo)。此時(shí)是從前向后遍歷還是從后向前遍歷呢？從前向后遍歷的話，遇到strNum[i - 1] > strNum[i]的情況，讓strNum[i - 1]減一，但此時(shí)如果strNum[i - 1]減一了，可能又小于strNum[i - 2]。這么說有點(diǎn)抽象，舉個(gè)例子，數(shù)字：332，從前向后遍歷的話，那么就把變成了329，此時(shí)2又小于了第一位的3了，真正的結(jié)果應(yīng)該是299。那么從后向前遍歷，就可以重復(fù)利用上次比較得出的結(jié)果了，從后向前遍歷332的數(shù)值變化為：332 -> 329 -> 299。

（2）后面所有元素變?yōu)?

? ? ? ? 從維護(hù)的位置開始，到整數(shù)末，每個(gè)數(shù)都變?yōu)?。

2.代碼實(shí)現(xiàn)

class Solution {
public:int monotoneIncreasingDigits(int n) {string s = to_string(n);int pos = s.size();//注意初值值設(shè)為數(shù)組末，以便找不到不符合單增性質(zhì)的位置時(shí)，//讓第二個(gè)循環(huán)不做for(int i=s.size()-1;i>0;i--){if(s[i-1] > s[i]){s[i-1]--;pos = i;}}for(int i=pos;i<s.size();i++){s[i] = '9';}return stoi(s);}
};

二、總結(jié)

1.貪心簡(jiǎn)單題

????????以下三道題目就是簡(jiǎn)單題，可以初步理解貪心的概念。

• 貪心算法：分發(fā)餅干(opens new window)
• 貪心算法：K次取反后最大化的數(shù)組和(opens new window)
• 貪心算法：檸檬水找零

2.貪心中等題?

（1）這兩類屬于第一次接觸較為難想的題，偏數(shù)學(xué)。

• 貪心算法：擺動(dòng)序列(opens new window)
• 貪心算法：單調(diào)遞增的數(shù)字

（2）貪心解決股票問題

? ? ? ? 一般的股票問題是動(dòng)規(guī)的領(lǐng)域，但部分用貪心也可以解決，以下是比較經(jīng)典的兩道可以貪心完成的股票問題。

• 貪心算法：買賣股票的最佳時(shí)機(jī)II(opens new window)
• 貪心算法：買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)?(opens new window)本題使用貪心算法比較繞，建議后面學(xué)習(xí)動(dòng)態(tài)規(guī)劃章節(jié)的時(shí)候，理解動(dòng)規(guī)就好

（3）兩個(gè)維度的題

????????在出現(xiàn)兩個(gè)維度相互影響的情況時(shí)，兩邊一起考慮一定會(huì)顧此失彼，要先確定一個(gè)維度，再確定另一個(gè)一個(gè)維度。

• 貪心算法：分發(fā)糖果(opens new window)
• 貪心算法：根據(jù)身高重建隊(duì)列

3.貪心難題

（1）貪心解決區(qū)間問題

????????主要是一些區(qū)間覆蓋問題，如何統(tǒng)計(jì)如何去除。

• 貪心算法：跳躍游戲(opens new window)
• 貪心算法：跳躍游戲II(opens new window)
• 貪心算法：用最少數(shù)量的箭引爆氣球(opens new window)
• 貪心算法：無重疊區(qū)間(opens new window)
• 貪心算法：劃分字母區(qū)間(opens new window)
• 貪心算法：合并區(qū)間

（2）無規(guī)律的題

貪心算法：最大子序和?(opens new window)

貪心算法：加油站?(opens new window)

4.總覽