LWC 61：738. Monotone Increasing Digits
LWC 61：738. Monotone Increasing Digits
LWC 61：738. Monotone Increasing Digits
传送门：738. Monotone Increasing Digits
Problem:
Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits. (Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)
Example 1:
Input: N = 10 Output: 9
Example 2:
Input: N = 1234 Output: 1234
Example 3:
Input: N = 332 Output: 299
Note:
N is an integer in the range [0, 10^9].
思路1： 求 <= N中，每一位大于等于前一位的最大num。无脑做法，不断减一，直到找到第一个符合Monotone定义的数。
超时版本：
public int monotoneIncreasingDigits(int N) {
int num = N;
while (!valid(String.valueOf(num))) {
num --;
}
return num;
}
boolean valid(String num) {
int n = num.length();
char[] cs = num.toCharArray();
for (int i = 1; i < n; ++i) {
if (cs[i] < cs[i - 1]) return false;
}
return true;
}显然遇到大数时会超时。
思路2： 举个例子，比如33296这个数，先看6，因为9比6大，显然不符合Monotone定义，所以为了满足求得最大的num，6一定变成9，且9减1，所以这个数就变成了33289，同理此时2和3是不符合定义，于是又变成了32999，还是一样，最终就变成了29999。
再看一个例子：23296，根据上述的过程则变为22999。所以只要对其中的每一位减一，后续的几位都变成9，生成多个候选解，那么必然有一个解在其中。
比如：
23296
可以生成：
1. 19999
2. 22999
3. 23199
4. 23289
取其符合Monotone定义的最大数即可Java版本：
public int monotoneIncreasingDigits(int N) {
int max = 0;
String num = String.valueOf(N);
int n = num.length();
for (int i = 0; i < n; ++i) {
StringBuilder sb = new StringBuilder(num.substring(0, i + 1));
int tmp = Integer.parseInt(sb.toString()) - 1;
StringBuilder ss = new StringBuilder(String.valueOf(tmp));
for (int j = i + 1; j < n; ++j) {
ss.append("9");
}
int cmp = Integer.parseInt(ss.toString());
if (valid(ss.toString()))
max = Math.max(max, cmp);
}
if (valid(num)) max = Math.max(max, N);
return max;
}
boolean valid(String num) {
int n = num.length();
char[] cs = num.toCharArray();
for (int i = 1; i < n; ++i) {
if (cs[i] < cs[i - 1]) return false;
}
return true;
}Python版本：
def monotoneIncreasingDigits(self, N):
"""
:type N: int
:rtype: int
"""
ans = 0
num = str(N)
n = len(num)
for i in range(n):
sb = num[0 : i + 1]
tmp = int(sb) - 1
ss = str(tmp)
for j in range(i + 1, n):
ss += '9'
cmp = int(ss)
if self.valid(ss):
ans = max(ans, cmp)
if self.valid(num):
ans = max(ans, N)
return ans
def valid(self, num):
n = len(num)
for i in range(1, n):
if num[i] < num[i - 1]:
return False
return True