738. 單調遞增的數字

當且僅當每個相鄰位數上的數字 x 和 y 滿足 x <= y 時，我們稱這個整數是單調遞增的。
給定一個整數 n ，返回 小于或等于 n 的最大數字，且數字呈 單調遞增 。

示例1：
輸入：n = 10
輸出：9
示例2：
輸入：n = 1234
輸出：1234

為了便于修改值，將其轉化為數組。

List<Integer> nums = new ArrayList<Integer>();
while (n > 0) {nums.add(0, n % 10);n /= 10;
}

從高位到低位單調遞增，從 0 開始判斷，是否是遞增的，當判斷第 i 位小于第 i - 1位時，將從第 i 位到最后一位修改為 9，并將第 i - 1 位減 1。
此時，第 i - 1 位減 1 后，可能會破壞前面 0 ~ i - 1 的遞增，需要往前進行處理，從 i - 1 開始往前遍歷，如果第 j 位大于等于第 j - 1 位，就不用繼續往前判斷了，前面一定是符合的，如果小于，就將第 j 位修改為 9，并將第 j - 1 位減一，減一就需要繼續判斷前面的遞增。

for (int i = 1; i < nums.size(); i++) {if (nums.get(i) < nums.get(i - 1)) {// 往后變為 9for (int j = i; j < nums.size(); j++) {nums.set(j, 9);}// 往前檢查nums.set(i - 1, nums.get(i- 1) - 1);for (int j = i - 1; j > 0; j--) {if (nums.get(j) >= nums.get(j - 1)) {break;}nums.set(j, 9);nums.set(j - 1, nums.get(j - 1) - 1);}break;}
}

最后將數組轉換為數字輸出。

int res = 0;
for (Integer num : nums) {res = res * 10 + num;
}

完整代碼

class Solution {public int monotoneIncreasingDigits(int n) {List<Integer> nums = new ArrayList<Integer>();while (n > 0) {nums.add(0, n % 10);n /= 10;}for (int i = 1; i < nums.size(); i++) {if (nums.get(i) < nums.get(i - 1)) {// 往后變為 9for (int j = i; j < nums.size(); j++) {nums.set(j, 9);}// 往前檢查nums.set(i - 1, nums.get(i- 1) - 1);for (int j = i - 1; j > 0; j--) {if (nums.get(j) >= nums.get(j - 1)) {break;}nums.set(j, 9);nums.set(j - 1, nums.get(j - 1) - 1);}break;}}int res = 0;for (Integer num : nums) {res = res * 10 + num;}return res;}
}