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

題目鏈接????
給定一個非負整數(shù) N，找出小于或等于 N 的最大的整數(shù)，同時這個整數(shù)需要滿足其各個位數(shù)上的數(shù)字是單調(diào)遞增。
（當且僅當每個相鄰位數(shù)上的數(shù)字 x 和 y 滿足 x <= y 時，我們稱這個整數(shù)是單調(diào)遞增的。）

示例 1:
輸入: N = 10
輸出: 9

示例 2:
輸入: N = 1234
輸出: 1234

示例 3:
輸入: N = 332
輸出: 299
說明: N 是在 [0, 10^9] 范圍內(nèi)的一個整數(shù)。

思路分析

暴力解法會超時。
題目要求小于等于N的最大單調(diào)遞增的整數(shù)，那么拿一個兩位的數(shù)字來舉例。

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

這一點如果想清楚了，這道題就好辦了。

此時是從前向后遍歷還是從后向前遍歷呢？

從前向后遍歷的話，遇到strNum[i - 1] > strNum[i]的情況，讓strNum[i - 1]減一，但此時如果strNum[i - 1]減一了，可能又小于strNum[i - 2]。

這么說有點抽象，舉個例子，數(shù)字：332，從前向后遍歷的話，那么就把變成了329，此時2又小于了第一位的3了，真正的結(jié)果應該是299。

那么從后向前遍歷，就可以重復利用上次比較得出的結(jié)果了，從后向前遍歷332的數(shù)值變化為：332 -> 329 -> 299

確定了遍歷順序之后，那么此時局部最優(yōu)就可以推出全局，找不出反例，試試貪心。

代碼實現(xiàn)

C++代碼如下：

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strNum = to_string(N);
        // flag用來標記賦值9從哪里開始
        // 設(shè)置為這個默認值，為了防止第二個for循環(huán)在flag沒有被賦值的情況下執(zhí)行
        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);
    }
};

我的：
我的是從前向后遍歷的，用一個maxindex來記錄目前出現(xiàn)過的最大的數(shù)（如果有332這種，就記錄第一個3，這樣結(jié)果是299，否則結(jié)果是329就不對了），其實maxindex就是記錄一旦出現(xiàn)遞減的數(shù)，該從哪里開始自減。文章來源地址http://www.zghlxwxcb.cn/news/detail-700730.html

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

到了這里，關(guān)于算法訓練day37|貪心算法 part06(LeetCode738.單調(diào)遞增的數(shù)字)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！