單調遞增的數字

給定一個非負整數

N

，找出小于或等于

N

的最大的整數，同時這個整數需要滿足其各個位數上的數字是單調遞增。當且僅當每個相鄰位數上的數字

x

和

y

滿足

x <= y

時，我們稱這個整數是單調遞增的。

示例

輸入: N = 10
輸出: 9
           

輸入: N = 1234
輸出: 1234
           

輸入: N = 332
輸出: 299
           

題解

/**
 * @param {number} N
 * @return {number}
 */
var monotoneIncreasingDigits = function(N) {
    let i = 1;
    let num = N;
    while(i*10 <= num){
        // console.log(i, num);
        // 每次取出兩位
        let n = ~~(num / i) % 100;  
        i = i * 10;
        if(~~(n/10) > n %10) num = ~~(num / i) * i - 1; 
        // 例如 1332 第一次循環之後是 取整(1332 / 10) * 10 - 1 = 1330 - 1 = 1329
        // 第二次循環就是 1300 - 1 = 1299
    }
    return num;
};
           

思路

整體思路就是将數字當作字元串，從尾到頭逆向周遊一遍，每次比較兩位，如果後一個位置上的數小于前一個位置上的數，那麼就将前邊的數減一，并将後邊的所有位都變為

9

，例如當我們周遊到了

1323

中比較

32

的這個位置上，此時

3 > 2

符合條件，那麼我們就将

3

減一并将其後的數都變作

9

，即将其變為

1299

，直到周遊到頭即可。通常來說可以把數字作為字元串來周遊處理，上面的題解是使用純數字的方式去做，首先定義

i

作為标記記錄周遊到到的位置，之後定義

num

作為待處理的數字，定義循環隻要能夠繼續取出兩位數就繼續循環，這是循環的終止條件，此外能夠使用乘法的地方就盡量不要使用除法，在

js

中

int32

如果不能夠整除則會自動轉雙精度

64

，是以在很多地方都需要強制轉數值為

int32

，之後取出兩位數，這裡

~~

是使用位運算強制轉了整型，在之後将

i * 10

定義到下一位，如果低一位上的值大于大于高一位上的值，那麼就将數值在第

i

位以後的值都變成

，然後減

1

即可達到上述的将此位減

1

以及之後的數字都變為

9

，可以參考上邊的示例，在循環結束後傳回處理的數字即可。

每日一題

https://github.com/WindrunnerMax/EveryDay
           

參考

https://leetcode-cn.com/problems/monotone-increasing-digits/