738. Monotone Increasing Digits
题目描述
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.)
|
|
Note: N is an integer in the range [0, 10^9].
题目大意
给定一整数N,找到小于等于N的最大单调递增数字。
解题思路
由高位到低位遍历整数N,找到第一个递减的数字。
记录最后一个连续相等的数字和下标记为v,直至第一个递减数字。例如12334551,我们只需要记录第一个5及其下标即可。
将v以后的所有数替换为0,再减一,加上递减之前的数字即可。
代码
|
|