贪心——738.单调递增的数字
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
示例 1:
- 输入: N = 10
- 输出: 9
示例 2:
- 输入: N = 1234
- 输出: 1234
示例 3:
- 输入: N = 332
- 输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。
首先把数字n按位，从小到大（从后往前）处理成list：
1 List<Integer> list = new ArrayList<>(); 2 while (n >= 1) { 3 list.add(n % 10); 4 n /= 10; 5 }
将当前的数n处理成比n小的最大“递增数“，关键就在于位数上的递增。
从n的每一位数从高到低来说，如果当前要比较的数字[index]和遍历到的数字[i]：
- 大于：当前数字符合递增要求，
index = i--;
- 等于：当前数字无法判断，需要遍历下一位数：
i--;
- 小于：
- 当前位数够减一：直接减
- 当前位数不够减：向前借位直到
- 够减一
- 第一位数（第一位数 >= 1，肯定够）
代码如下：
1 class Solution { 2 public int monotoneIncreasingDigits(int n) { 3 List<Integer> list = new ArrayList<>(); 4 while (n >= 1) { 5 list.add(n % 10); 6 n /= 10; 7 } 8 //count == 位数，index == 判断的位数 9 int count = list.size(), index = count - 1, i = count - 2; 10 while (i >= 0) { 11 if (list.get(i) > list.get(index)) { 12 index = i--; 13 } else if (list.get(i) < list.get(index)) { 14 //向前借位（可向前0位），直到当前数字够-1 or 到了第一位（借位到了第一位，第一位数字必定 >= 1，肯定够） 15 while (list.get(index) == 0 && index > 0) { 16 --index; 17 } 18 //当前位数-1 19 list.set(index, list.get(index)-1); 20 //从-1位数的后一位开始，每一位数都是9 21 --index; 22 while (index >= 0) { 23 list.set(index--, 9); 24 } 25 break; 26 } else { 27 --i; 28 } 29 } 30 31 int result = 0, base = 1; 32 i = 0; 33 while (i < count) { 34 result += list.get(i++) * base; 35 base *= 10; 36 } 37 return result; 38 } 39 }
时间：O(n)
空间：O(1)（除了返回值无须额外空间）
