[[439817]]

單調遞增的數字

力扣題目鏈接：https://leetcode-cn.com/problems/monotone-increasing-digits

給定一個非負整數 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; 
    } 
}; 

• 時間復雜度：O(n * m) m為n的數字長度
• 空間復雜度：O(1)

貪心算法

題目要求小于等于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); 
    } 
}; 

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

總結

本題只要想清楚個例，例如98，一旦出現strNum[i - 1] > strNum[i]的情況(非單調遞增)，首先想讓strNum[i - 1]減一，strNum[i]賦值9，這樣這個整數就是89。就可以很自然想到對應的貪心解法了。

想到了貪心，還要考慮遍歷順序，只有從后向前遍歷才能重復利用上次比較的結果。

最后代碼實現的時候，也需要一些技巧，例如用一個flag來標記從哪里開始賦值9。

其他語言版本

Java：

版本1 
class Solution { 
    public int monotoneIncreasingDigits(int N) { 
        String[] strings = (N + "").split(""); 
        int start = strings.length; 
        for (int i = strings.length - 1; i > 0; i--) { 
            if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) { 
                strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + ""; 
                start = i; 
            } 
        } 
        for (int i = start; i < strings.length; i++) { 
            strings[i] = "9"; 
        } 
        return Integer.parseInt(String.join("",strings)); 
    } 
} 

java版本1中創建了String數組，多次使用Integer.parseInt了方法，這導致不管是耗時還是空間占用都非常高，用時12ms，下面提供一個版本在char數組上原地修改，用時1ms的版本

版本2 
class Solution { 
    public int monotoneIncreasingDigits(int n) { 
        if (n==0)return 0; 
        char[] chars= Integer.toString(n).toCharArray(); 
        int start=Integer.MAX_VALUE;//start初始值設為最大值，這是為了防止當數字本身是單調遞增時，沒有一位數字需要改成9的情況 
        for (int i=chars.length-1;i>0;i--){ 
            if (chars[i]<chars[i-1]){ 
                chars[i-1]--; 
                start=i; 
            } 
        } 
        StringBuilder res=new StringBuilder(); 
        for (int i=0;i<chars.length;i++){ 
            if (chars[i]=='0'&&i==0)continue;//防止出現09這樣的情況 
            if (i>=start){ 
                res.append('9'); 
            }else res.append(chars[i]); 
        } 
        return Integer.parseInt(res.toString()); 
    } 
} 

Python：

class Solution: 
    def monotoneIncreasingDigits(self, n: int) -> int: 
        a = list(str(n)) 
        for i in range(len(a)-1,0,-1): 
            if int(a[i]) < int(a[i-1]): 
                a[i-1] = str(int(a[i-1]) - 1) 
                a[i:] = '9' * (len(a) - i)  #python不需要設置flag值，直接按長度給9就好了 
        return int("".join(a)) 

Go

func monotoneIncreasingDigits(N int) int { 
    s := strconv.Itoa(N)//將數字轉為字符串，方便使用下標 
    ss := []byte(s)//將字符串轉為byte數組，方便更改。 
    n := len(ss) 
    if n <= 1 { 
        return N 
    } 
    for i:=n-1 ; i>0; i-- { 
        if ss[i-1] > ss[i] {//前一個大于后一位,前一位減1，后面的全部置為9 
            ss[i-1] -= 1 
            for j := i ; j < n; j++ {//后面的全部置為9 
                ss[j] = '9' 
            } 
        } 
    } 
    res, _ := strconv.Atoi(string(ss)) 
    return res 
} 

Javascript

var monotoneIncreasingDigits = function(n) { 
    n = n.toString() 
    n = n.split('').map(item => { 
        return +item 
    }) 
    let flag = Infinity 
    for(let i = n.length - 1; i > 0; i--) { 
        if(n [i - 1] > n[i]) { 
            flag = i 
            n[i - 1] = n[i - 1] - 1 
            n[i] = 9 
        } 
    } 
 
    for(let i = flag; i < n.length; i++) { 
        n[i] = 9 
    } 
 
    n = n.join('') 
    return +n 
};