# LWC 61：738. Monotone Increasing Digits

## LWC 61：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].

```    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;
}```

```23296

1. 19999
2. 22999
3. 23199
4. 23289

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   ```

0 条评论

• ### LWC 59：728. Self Dividing Numbers

LWC 59：728. Self Dividing Numbers 传送门：728. Self Dividing Numbers Problem: A sel...

• ### 算法细节系列（32）：有趣的数学

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### LWC 71: 782. Transform to Chessboard

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 1019 数字黑洞 (20 分)

给定任一个各位数字不完全相同的 4 位正整数，如果我们先把 4 个数字按非递增排序，再按非递减排序，然后用第 1 个数字减第 2 个数字，将得到一个新的数字。一...

• ### 【LeetCode】221. 最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

• ### Unique Paths

问题：从起点到终点总共有多少条路径 分析：f[x,y]=f[x+1,y]+f[x,y+1]，用记忆化搜索就可以解决了 class Solution { publ...

• ### 剑指offer（61-67）题解

例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树

• ### Java工具集-数学(阶乘函数)

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### hust Dating With Girls

http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=573#problem/B 题意：求最大权...