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
.)
Example 1:
Input: N = 10 Output: 9
Example 2:
Input: N = 1234 Output: 1234
Example 3:
Input: N = 332 Output: 299
Note:
-----------------------------N
is an integer in the range [0, 10^9]
.重点是找到breakPoint, 多列几个test case就能明白怎么写了
7752 -> 6999
1541 -> 1499
85 -> 79
941 -> 899
分三步
1. 找到拐点
2. 拐点位置之前重新找拐点,新拐点位置之前所有值减1
3. 新拐点之后所有位置上的值为9
class Solution { public int monotoneIncreasingDigits(int N) { int[] arr = convertToArray(N); int i = getBreakPoint(arr); i = updateBeforeBreakPoint(arr, i); return getFinalNumber(arr, i); } private int getFinalNumber(int[] arr, int i) { int rt = 0; for (int j = 0; j < 9; j++) { if (j >= i + 1) { rt = 9 + rt * 10; }else if (arr[j] != 0) { rt = arr[j] + rt * 10; } } return rt; } private int updateBeforeBreakPoint(int[] arr, int i) { while (i > 0 && i < 9) { if (arr[i] >= arr[i - 1]) { break; } arr[i - 1] = arr[i - 1] - 1; i--; } return i; } private int getBreakPoint(int[] arr) { int i = 1; while (i < 9) { if (arr[i] < arr[i - 1]) { break; } i++; } return i; } private int[] convertToArray(int N) { int[] arr = new int[9]; for (int i = 8; i >= 0; i--) { arr[i] = N % 10; N /= 10; } return arr; } }
流弊写法,从后往前
credit: barkfanleen3@gmail.com
class Solution { public int monotoneIncreasingDigits(int N) { int res = 0; int pre = Integer.MAX_VALUE; int offset =1; while(N != 0) { int digit = N % 10; if(digit > pre) { res = digit * offset - 1; pre = digit -1; }else { res = res + digit * offset; pre = digit; } offset *= 10; N = N/10; } return res; } }
No comments:
Post a Comment