Monotone Increasing Digits
Problem
Given an integer n, return the largest integer less than or equal to n whose digits are monotonically non-decreasing from left to right.
n=332299def monotoneIncreasingDigits(n):
s = list(str(n))
k = len(s)
for i in range(len(s) - 1, 0, -1):
if s[i - 1] > s[i]:
s[i - 1] = chr(ord(s[i - 1]) - 1)
k = i
for i in range(k, len(s)): s[i] = '9'
return int(''.join(s))function monotoneIncreasingDigits(n) {
const s = String(n).split('');
let k = s.length;
for (let i = s.length - 1; i > 0; i--) {
if (s[i - 1] > s[i]) {
s[i - 1] = String.fromCharCode(s[i - 1].charCodeAt(0) - 1);
k = i;
}
}
for (let i = k; i < s.length; i++) s[i] = '9';
return parseInt(s.join(''));
}class Solution {
public int monotoneIncreasingDigits(int n) {
char[] s = Integer.toString(n).toCharArray();
int k = s.length;
for (int i = s.length - 1; i > 0; i--) {
if (s[i - 1] > s[i]) { s[i - 1]--; k = i; }
}
for (int i = k; i < s.length; i++) s[i] = '9';
return Integer.parseInt(new String(s));
}
}class Solution {
public:
int monotoneIncreasingDigits(int n) {
string s = to_string(n);
int k = s.size();
for (int i = s.size() - 1; i > 0; i--) {
if (s[i - 1] > s[i]) { s[i - 1]--; k = i; }
}
for (int i = k; i < (int)s.size(); i++) s[i] = '9';
return stoi(s);
}
};Explanation
We want the biggest number <= n whose digits never decrease left to right. A digit "drop" (a place where a digit is bigger than the one after it) is exactly what breaks the rule, so we hunt those down.
The trick: scan the digits from right to left. Whenever digit i-1 is greater than digit i, we have a drop. We fix it by lowering the left digit by 1 and remembering this spot as k — the position from which everything to the right should later become 9.
Why scan right to left? Lowering a digit can create a new drop with the digit before it (for example 332 → lowering the middle 3 to a 2 makes 322, still a drop earlier). Going right to left lets that decrement propagate leftward and always lands on the correct, earliest cliff.
After finding the final cliff k, we set every digit from k onward to 9. That keeps the number non-decreasing while making it as large as possible.
Example: n = 332. From the right, 3 > 2 at the last pair, so lower that 3 and set k. The decrement propagates: the leading 3 becomes 2, and the rest become 9s, giving 299.