738.單調遞增的數字
給定一個非負整數 N，找出小於或等於 N 的最大的整數，同時這個整數需要滿足其各個位數上的數字是單調遞增。
（當且僅當每個相鄰位數上的數字 x 和 y 滿足 x <= y 時，我們稱這個整數是單調遞增的。）
示例 1:輸入: N = 10輸出: 9
示例 2:輸入: N = 1234輸出: 1234
示例 3:輸入: N = 332輸出: 299
說明: N 是在 [0, 10^9] 範圍內的一個整數。
思路暴力解法題意很簡單，那麼首先想的就是暴力解法了，來我提大家暴力一波，結果自然是超時！
程式碼如下：
class Solution {private: 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; }};題目要求小於等於N的最大單調遞增的整數，那麼拿一個兩位的數字來舉例。
例如：98，一旦出現strNum[i - 1] > strNum[i]的情況（非單調遞增），首先想讓strNum[i - 1]--，然後strNum[i]給為9，這樣這個整數就是89，即小於98的最大的單調遞增整數。
這一點如果想清楚了，這道題就好辦了。
區域性最優：遇到strNum[i - 1] > strNum[i]的情況，讓strNum[i - 1]--，然後strNum[i]給為9，可以保證這兩位變成最大單調遞增整數。
全域性最優：得到小於等於N的最大單調遞增的整數。
但這裡區域性最優推出全域性最優，還需要其他條件，即遍歷順序，和標記從哪一位開始統一改成9。
此時是從前向後遍歷還是從後向前遍歷呢？
從前向後遍歷的話，遇到strNum[i - 1] > strNum[i]的情況，讓strNum[i - 1]減一，但此時如果strNum[i - 1]減一了，可能又小於strNum[i - 2]。
這麼說有點抽象，舉個例子，數字：332，從前向後遍歷的話，那麼就把變成了329，此時2又小於了第一位的3了，真正的結果應該是299。
所以從前後向遍歷會改變已經遍歷過的結果！
那麼從後向前遍歷，就可以重複利用上次比較得出的結果了，從後向前遍歷332的數值變化為：332 -> 329 -> 299
確定了遍歷順序之後，那麼此時區域性最優就可以推出全域性，找不出反例，試試貪心。
C++程式碼如下：
class Solution {public: int monotoneIncreasingDigits(int N) { string strNum = to_string(N); // flag用來標記賦值9從哪裡開始 // 設定為這個預設值，為了防止第二個for迴圈在flag沒有被賦值的情況下執行 int flag = strNum.size(); for (int i = strNum.size() - 1; i > 0; i--) { if (strNum[i - 1] > strNum[i] ) { flag = i; strNum[i - 1]--; } } for (int i = flag; i < strNum.size(); i++) { strNum[i] = '9'; } return stoi(strNum); }};本題只要想清楚個例，例如98，一旦出現strNum[i - 1] > strNum[i]的情況（非單調遞增），首先想讓strNum[i - 1]減一，strNum[i]賦值9，這樣這個整數就是89。就可以很自然想到對應的貪心解法了。
想到了貪心，還要考慮遍歷順序，只有從後向前遍歷才能重複利用上次比較的結果。
最後程式碼實現的時候，也需要一些技巧，例如用一個flag來標記從哪裡開始賦值9。
我是程式設計師Carl，個人主頁：https://github.com/youngyangyang04
這裡每天8:35準時推送一道經典演算法題目，我選擇的每道題目都不是孤立的，而是由淺入深，環環相扣，幫你梳理演算法知識脈絡，輕鬆學演算法！