LeetCode 738. 单调递增的数字

Categories:

题目描述
思路分析
1. 解法一：从右向左贪心（推荐）
相似题目

题目描述

✅ 738. 单调递增的数字

思路分析

解法一：从右向左贪心（推荐）

核心思路：

从右向左扫描，若发现 digits[i] > digits[i+1]，则将 digits[i]--。

并记录位置 mark，将 mark 之后的所有数字置为 9。

最终得到不超过 N 的最大单调递增数字。

复杂度分析：

时间复杂度：O(k)，其中 k 表示数字位数。

空间复杂度：O(k)。

class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] digits = String.valueOf(n).toCharArray();
        int mark = digits.length;

        for (int i = digits.length - 2; i >= 0; i--) {
            if (digits[i] > digits[i + 1]) {
                digits[i]--;
                mark = i + 1;
            }
        }

        for (int i = mark; i < digits.length; i++) {
            digits[i] = '9';
        }

        return Integer.parseInt(new String(digits));
    }
}

import "strconv"

func monotoneIncreasingDigits(n int) int {
	digits := []byte(strconv.Itoa(n))
	mark := len(digits)

	for i := len(digits) - 2; i >= 0; i-- {
		if digits[i] > digits[i+1] {
			digits[i]--
			mark = i + 1
		}
	}

	for i := mark; i < len(digits); i++ {
		digits[i] = '9'
	}

	res, _ := strconv.Atoi(string(digits))
	return res
}

相似题目

题目	难度	考察点
738. 单调递增的数字	中等	贪心
402. 移掉 K 位数字	中等	贪心
665. 非递减数列	中等	贪心
1328. 破坏回文串	中等	贪心
968. 监控二叉树	困难	贪心
376. 摆动序列	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/61167177