Day31 | Part6
约 90 个字 26 行代码 预计阅读时间 1 分钟
暴力: TLE → 249/308 cases passed(N/A)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | bool check(int num) { // 看num是否为递增
if(num < 10) return true;
int max = 10;
while(num) {
int t = num % 10;
if(max >= t) max = t;
else return false;
num /= 10;
}
return true;
}
int monotoneIncreasingDigits(int n) {
for(int i = n; i > 0; i --)
if(check(i)) return i;
return 0;
}
|
比如98先转为字符串，若出现strNum[i - 1] > strNum[i]的情况（非单调递增）
- 先让
strNum[i - 1]--，然后strNum[i]给为9，整数即89
- 即小于98的最大的单调递增整数为89
| int monotoneIncreasingDigits(int n) {
string str = to_string(n); // int --> string
int flag = str.size(); // flag用来标记赋值9从哪里开始
for(int i = str.size() - 1; i > 0; i--)
if(str[i - 1] > str[i]) // 若不是逆序了
flag = i, str[i - 1] --;
for(int i = flag; i < str.size(); i ++)
str[i] = '9';
return stoi(str);
}
|
贪心和二叉树的一个结合 (难) → 参考
