题目

当且仅当每个相邻位数上的数字 x 和y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1:

  1. 输入: n = 10
  2. 输出: 9

示例 2:

  1. 输入: n = 1234
  2. 输出: 1234

示例 3:

  1. 输入: n = 332
  2. 输出: 299

提示:

  • 0 <= n <= 10^9

    解题方法

    将整数n按位从高到低保存为数组，当连续两位i, i-1出现nums[i-1] > nums[i]时，通常的做法是对nums[i-1]减1，将nums[i]置为9，此时为了保证最后的数字最大，需要将i以后的所有位都置为9。因此从后向前遍历各位，记录需要置为9的最高位，并将其后所有数字都置为9。
    时间复杂度O(n)，空间复杂度O(1)。
    C++代码：

    1. class Solution {
    2. public:
    3.   int monotoneIncreasingDigits(int n) {
    4.       int nums[10] = {0};
    5.       for(int i=9; i>=0; i--) {
    6.           nums[i] = n%10;
    7.           n /= 10;
    8.       }
    9.       int last = INT_MAX;
    10.       int result = 0;
    11.       for(int i=9; i>0; i--) {
    12.           if(nums[i-1]>nums[i]) {
    13.               nums[i-1]--;
    14.               last = i;
    15.           }
    16.       }
    17.       for(int i=0; i<10; i++) {
    18.           if(i<last) result = result*10 + nums[i];
    19.           else result = result*10 + 9;
    20.       } 
    22.       return result;
    23.   }
    24. };