题目链接
贪心
class Solution {
public int monotoneIncreasingDigits(int n) {
char[] digits = String.valueOf(n).toCharArray();
int flag = digits.length;
for (int i = digits.length - 1; i > 0; i--) {
if (digits[i] < digits[i - 1]) {
flag = i;
digits[i - 1]--;
}
}
for (int i = flag; i < digits.length; i++) {
digits[i] = '9';
}
return Integer.parseInt(new String(digits));
}
}
本题使用暴力法会超时,贪心的思想为:
对给出的数字从后向前遍历,如果不符合单调递增则将不符合的位数字-1,之后的数字全部变为9