貪心——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)（除了返回值無須額外空間）
