目錄

738.單調遞增的數(shù)字

方法一：暴力解法

?方法二：貪心解法

貪心算法總結

---

738.單調遞增的數(shù)字

題目鏈接

文章鏈接

方法一：暴力解法

class Solution {
private:// 各位遞增判斷函數(shù)bool checkNum(int num) {int max = 10;while (num) {int t = num % 10;if (max >= t) max = t;else return false;num = num / 10;}return true;}
public:int monotoneIncreasingDigits(int N) {for (int i = N; i > 0; i--) { // 從大到小遍歷if (checkNum(i)) return i;}return 0;}
};

?方法二：貪心解法

? ? ? ? ?要注意相鄰位置比較的邏輯實現(xiàn)和前后遍歷順序，只有從后向前遍歷才能減少處理因為前一個相鄰元素處理后改變的新值對當前值判斷的影響。

class Solution {
public:int monotoneIncreasingDigits(int n) {string strNum = to_string(n);int flag = strNum.size();for (int i = strNum.size() - 1; i > 0; i--){if (strNum[i - 1] > strNum[i]) {strNum[i - 1]--;flag = i;}}for (int i = flag; i < strNum.size(); i++) {strNum[i] = '9';}return stoi(strNum);}
};

貪心算法總結

? ? ? ? 在貪心算法題的練習過程中，雖然沒有能夠總結出能夠直接套用的模板，但是還是對于不同難度的貪心算法題有了大概的認識。

? ? ? ? 首先是一些簡單題，基本上通過常識就能解決不用想具體的局部最優(yōu)和全局最優(yōu)。

? ? ? ? 對于一些中等題，貪心算法就展現(xiàn)出它的巧妙之處了，對于類似重疊區(qū)間的題目，利用貪心實現(xiàn)由固定的套路；對于要同時考慮兩個維度的題目，往往先選擇一個合適的維度進行討論，再考慮選擇另一個維度討論補充。

? ? ? ? 對于一些貪心難題，例如和二叉樹等較難的數(shù)據結構關聯(lián)起來，處理起來就相當麻煩，在一刷的時候我選擇跳過。