Monotonic Increasing Digits#

Given a non-negative integer N, find the largest integer less than or equal to N that has monotone increasing digits. An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.

Example#

Solution#

/**
 * @param {number} N
 * @return {number}
 */
var monotoneIncreasingDigits = function(N) {
    let i = 1;
    let num = N;
    while(i*10 <= num){
        let n = ~~(num / i) % 100;  
        i = i * 10;
        if(~~(n/10) > n %10) num = ~~(num / i) * i - 1; 
    }
    return num;
};

Idea#

The idea is to treat the number as a string and traverse it from the end to the beginning. Compare each pair of digits, if the digit at the later position is less than the digit at the former position, then decrease the former digit by one and change all the digits after it to 9. For example, when we traverse the number 1323 and compare the position of 32, since 3 > 2, we decrease 3 by one and change all the digits after it to 9, thus making it 1299. We continue this process until we reach the beginning.

Generally, we can traverse and handle numbers as strings. However, the given solution uses a purely numerical approach. First, i is defined as a marker to record the position being traversed, and then num is defined as the number to be processed. The loop continues as long as it can still extract two digits. This is the termination condition of the loop. Additionally, use multiplication wherever possible to avoid division. In JavaScript, int32 will automatically convert to double precision 64 if it cannot be evenly divided, so in many places, numerical values need to be forcefully converted to int32. Then, extract two digits. Here, ~~ uses bitwise operation to forcibly convert to an integer. Then, define i * 10 to the next position. If the value in the lower position is greater than the value in the higher position, then set the value of the number after the ith digit to 0 and then subtract 1 to achieve the aforementioned operation of decreasing this digit by 1 and turning all the subsequent digits into 9. You can refer to the example above, and finally return the processed number after the loop ends.

Daily Exercise#

Reference#