0738.单调递增的数字
参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！
# 738.单调递增的数字 [力扣题目链接](https://leetcode.cn/problems/monotone-increasing-digits/) 给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。 （当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。） 示例 1: * 输入: N = 10 * 输出: 9 示例 2: * 输入: N = 1234 * 输出: 1234 示例 3: * 输入: N = 332 * 输出: 299 说明: N 是在 [0, 10^9] 范围内的一个整数。 ## 算法公开课 **[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：[贪心算法，思路不难想，但代码不好写！LeetCode:738.单调自增的数字](https://www.bilibili.com/video/BV1Kv4y1x7tP)，相信结合视频在看本篇题解，更有助于大家对本题的理解**。 ## 思路 ### 暴力解法 题意很简单，那么首先想的就是暴力解法了，来我替大家暴力一波，结果自然是超时！ 代码如下：class Solution {
private:
// 判断一个数字的各位上是否是递增
bool checkNum(int num) {
int max = 10;
while (num) {
int t = num % 10;
if (max >= t) max = t;
else return false;
num = num / 10;
}
return true;
}
public:
int monotoneIncreasingDigits(int N) {
for (int i = N; i > 0; i--) { // 从大到小遍历
if (checkNum(i)) return i;
}
return 0;
}
};
class Solution {
public:
int monotoneIncreasingDigits(int N) {
string strNum = to_string(N);
// flag用来标记赋值9从哪里开始
// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
int flag = strNum.size();
for (int i = strNum.size() - 1; i > 0; i--) {
if (strNum[i - 1] > strNum[i] ) {
flag = i;
strNum[i - 1]--;
}
}
for (int i = flag; i < strNum.size(); i++) {
strNum[i] = '9';
}
return stoi(strNum);
}
};
版本1
class Solution {
public int monotoneIncreasingDigits(int N) {
String[] strings = (N + "").split("");
int start = strings.length;
for (int i = strings.length - 1; i > 0; i--) {
if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {
strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
start = i;
}
}
for (int i = start; i < strings.length; i++) {
strings[i] = "9";
}
return Integer.parseInt(String.join("",strings));
}
}
版本2
class Solution {
public int monotoneIncreasingDigits(int n) {
String s = String.valueOf(n);
char[] chars = s.toCharArray();
int start = s.length();
for (int i = s.length() - 2; i >= 0; i--) {
if (chars[i] > chars[i + 1]) {
chars[i]--;
start = i+1;
}
}
for (int i = start; i < s.length(); i++) {
chars[i] = '9';
}
return Integer.parseInt(String.valueOf(chars));
}
}
class Solution:
def checkNum(self, num):
max_digit = 10
while num:
digit = num % 10
if max_digit >= digit:
max_digit = digit
else:
return False
num //= 10
return True
def monotoneIncreasingDigits(self, N):
for i in range(N, 0, -1):
if self.checkNum(i):
return i
return 0
class Solution:
def monotoneIncreasingDigits(self, N: int) -> int:
# 将整数转换为字符串
strNum = str(N)
# flag用来标记赋值9从哪里开始
# 设置为字符串长度，为了防止第二个for循环在flag没有被赋值的情况下执行
flag = len(strNum)
# 从右往左遍历字符串
for i in range(len(strNum) - 1, 0, -1):
# 如果当前字符比前一个字符小，说明需要修改前一个字符
if strNum[i - 1] > strNum[i]:
flag = i # 更新flag的值，记录需要修改的位置
# 将前一个字符减1，以保证递增性质
strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i:]
# 将flag位置及之后的字符都修改为9，以保证最大的递增数字
for i in range(flag, len(strNum)):
strNum = strNum[:i] + '9' + strNum[i + 1:]
# 将最终的字符串转换回整数并返回
return int(strNum)
class Solution:
def monotoneIncreasingDigits(self, N: int) -> int:
# 将整数转换为字符串
strNum = list(str(N))
# 从右往左遍历字符串
for i in range(len(strNum) - 1, 0, -1):
# 如果当前字符比前一个字符小，说明需要修改前一个字符
if strNum[i - 1] > strNum[i]:
strNum[i - 1] = str(int(strNum[i - 1]) - 1) # 将前一个字符减1
# 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质
for j in range(i, len(strNum)):
strNum[j] = '9'
# 将列表转换为字符串，并将字符串转换为整数并返回
return int(''.join(strNum))
class Solution:
def monotoneIncreasingDigits(self, N: int) -> int:
# 将整数转换为字符串
strNum = list(str(N))
# 从右往左遍历字符串
for i in range(len(strNum) - 1, 0, -1):
# 如果当前字符比前一个字符小，说明需要修改前一个字符
if strNum[i - 1] > strNum[i]:
strNum[i - 1] = str(int(strNum[i - 1]) - 1) # 将前一个字符减1
# 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质
strNum[i:] = '9' * (len(strNum) - i)
# 将列表转换为字符串，并将字符串转换为整数并返回
return int(''.join(strNum))
class Solution:
def monotoneIncreasingDigits(self, N: int) -> int:
strNum = str(N)
for i in range(len(strNum) - 1, 0, -1):
# 如果当前字符比前一个字符小，说明需要修改前一个字符
if strNum[i - 1] > strNum[i]:
# 将前一个字符减1，以保证递增性质
# 使用字符串切片操作将修改后的前面部分与后面部分进行拼接
strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + '9' * (len(strNum) - i)
return int(strNum)
func monotoneIncreasingDigits(N int) int {
s := strconv.Itoa(N)//将数字转为字符串，方便使用下标
ss := []byte(s)//将字符串转为byte数组，方便更改。
n := len(ss)
if n <= 1 {
return N
}
for i := n-1; i > 0; i-- {
if ss[i-1] > ss[i] { //前一个大于后一位,前一位减1，后面的全部置为9
ss[i-1] -= 1
for j := i; j < n; j++ { //后面的全部置为9
ss[j] = '9'
}
}
}
res, _ := strconv.Atoi(string(ss))
return res
}
var monotoneIncreasingDigits = function(n) {
n = n.toString()
n = n.split('').map(item => {
return +item
})
let flag = Infinity
for(let i = n.length - 1; i > 0; i--) {
if(n [i - 1] > n[i]) {
flag = i
n[i - 1] = n[i - 1] - 1
n[i] = 9
}
}
for(let i = flag; i < n.length; i++) {
n[i] = 9
}
n = n.join('')
return +n
};
function monotoneIncreasingDigits(n: number): number {
let strArr: number[] = String(n).split('').map(i => parseInt(i));
const length = strArr.length;
let flag: number = length;
for (let i = length - 2; i >= 0; i--) {
if (strArr[i] > strArr[i + 1]) {
strArr[i] -= 1;
flag = i + 1;
}
}
for (let i = flag; i < length; i++) {
strArr[i] = 9;
}
return parseInt(strArr.join(''));
};
object Solution {
import scala.collection.mutable
def monotoneIncreasingDigits(n: Int): Int = {
var digits = mutable.ArrayBuffer[Int]()
// 提取每位数字
var temp = n // 因为 参数n 是不可变量所以需要赋值给一个可变量
while (temp != 0) {
digits.append(temp % 10)
temp = temp / 10
}
// 贪心
var flag = -1
for (i <- 0 until (digits.length - 1) if digits(i) < digits(i + 1)) {
flag = i
digits(i + 1) -= 1
}
for (i <- 0 to flag) digits(i) = 9
// 拼接
var res = 0
for (i <- 0 until digits.length) {
res += digits(i) * math.pow(10, i).toInt
}
res
}
}
impl Solution {
pub fn monotone_increasing_digits(n: i32) -> i32 {
let mut n_bytes = n.to_string().into_bytes();
let mut flag = n_bytes.len();
for i in (1..n_bytes.len()).rev() {
if n_bytes[i - 1] > n_bytes[i] {
flag = i;
n_bytes[i - 1] -= 1;
}
}
for v in n_bytes.iter_mut().skip(flag) {
*v = 57;
}
n_bytes
.into_iter()
.fold(0, |acc, x| acc * 10 + x as i32 - 48)
}
}
