Monotone Increasing Digits Problem
Description
LeetCode Problem 738.
An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.
Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.
Example 1:
1
2
Input: n = 10
Output: 9
Example 2:
1
2
Input: n = 1234
Output: 1234
Example 3:
1
2
Input: n = 332
Output: 299
Constraints:
- 0 <= n <= 10^9
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int monotoneIncreasingDigits(int N) {
string n_str = to_string(N);
int marker = n_str.size();
for (int i = n_str.size()-1; i > 0; i --) {
if (n_str[i] < n_str[i-1]) {
marker = i;
n_str[i-1] = n_str[i-1]-1;
}
}
for (int i = marker; i < n_str.size(); i ++)
n_str[i] = '9';
return stoi(n_str);
}
};