監控二叉樹同樣的等代碼隨想錄刷完后，再回頭來看，先跳過

?738.單調遞增的數字

代碼隨想錄

解題思路

例如：98，一旦出現strNum[i - 1] > strNum[i]的情況（非單調遞增），首先想讓strNum[i - 1]--，然后strNum[i]給為9，這樣這個整數就是89，即小于98的最大的單調遞增整數

遍歷順序就是從后往前的，如果是從前從后的話，332就會變成329就不對了。?

這里我們還需要利用flag來記錄我們需要變成9的位置，例如1000，如果不記錄就會變成0900的情況?

這里處理位數，是使用tostring和stoi來操作的，比較方便

class Solution {
public:int monotoneIncreasingDigits(int n) {string str = to_string(n);int flag = str.size();for(int i = str.size()-1; i >0 ; i--){if(str[i-1]>str[i]){//前一位大于后一位str[i-1]--;flag = i;   //記錄的是從哪一位開始都變成9}}for(int i = flag ; i<str.size() ; i++){str[i] = '9';}return stoi(str);}
};

• 時間復雜度：O(n)，n 為數字長度
• 空間復雜度：O(n)，需要一個字符串，轉化為字符串操作更方便

貪心總結

代碼隨想錄

收獲

貪心算法草草完事了，還是有很多沒吃透，還需要二刷