0738. Monotone Increasing Digits¶
题目信息¶
- 题号:
0738
- 难度:
Medium
- 主题:
数学、十进制数位、单调性
- 原题:
- 重点:
十进制数位从左到右必须非递减;返回不超过
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 本身就是最大合法答案。