0738. Monotone Increasing Digits

题目信息

题号:

0738

难度:

Medium

主题:

数学、十进制数位、单调性

原题:

LeetCode 0738

重点:

十进制数位从左到右必须非递减;返回不超过 n 的最大满足条件整数,0 也属于合法输入

题目重述

若一个非负整数的十进制表示中,每一对相邻数位从左到右都满足前一位小于或等于后一位,则称它具有单调递增数位。

给定整数 n,返回所有不大于 n 且具有单调递增数位的整数中的最大值。这里的“递增”允许相邻数位相等,结果按普通整数表示,不保留前导零。

0 <= n <= 10^9。

自建示例

中间数位破坏单调性:

输入:n = 120
输出:119
解释:120 的数位 2 后面出现 0,不满足非递减条件;119 的数位满足 1 <= 1 <= 9,并且它是不超过 120 的最大合法整数。

需要减少最高位:

输入:n = 1000
输出:999
解释:1000 不满足数位非递减条件。999 满足 9 <= 9 <= 9,且不存在更大的合法整数仍不超过 1000。

输入达到允许的最小值:

输入:n = 0
输出:0
解释:0 的十进制表示只有一个数位,不存在违反非递减要求的相邻数位,因此 0 本身就是最大合法答案。