blob: 843db3551e4e2c84cd2d1e54d3db334c7b1f9378 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
// 738. Monotone Increasing Digits
#include "leetcode.h"
/*
* an integer has monotone increasing digits if and only if each pair of
* adjacent digts 'x' and 'y' satisfy 'x <= y'. given an integer 'n', return the
* largest number that is less than or equal to 'n' with monotone inccreasing
* digits
*/
char *int_to_str(int n) {
char *res = malloc(11);
int val = n, idx = 0;
while (val) {
res[idx] = val % 10 + '0';
val /= 10;
idx++;
}
res[idx] = '\0';
for (int i = 0; i < idx / 2; i++) {
char tmp = res[i];
res[i] = res[idx - 1 - i];
res[idx - 1 - i] = tmp;
}
return res;
}
int str_to_int(char *s) {
int n = strlen(s), val = 0;
for (int i = 0; i < n; i++)
val *= 10 + s[i] - '0';
return val;
}
int monotoneIncreasingDigits(int n) {
char *s = int_to_str(n);
int j = strlen(s), k = j;
for (int i = k - 1; i; i--) {
if (s[i] >= s[i - 1])
continue;
s[i - 1]--;
j = i;
}
for (int i = j; i < k; i++)
s[i] = '9';
return str_to_int(s);
}
int main() {
printf("%d\n", monotoneIncreasingDigits(10)); // expect: 9
printf("%d\n", monotoneIncreasingDigits(1234)); // expect: 1234
printf("%d\n", monotoneIncreasingDigits(332)); // expect: 299
}
|