https://leetcode.com/problems/monotone-increasing-digits/solution/
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].
X.
One initial thought that comes to mind is we can always have a candidate answer of
d999...9 (a digit 0 <= d <= 9 followed by some number of nines.) For example if N = 432543654, we could always have an answer of at least 399999999.
We can do better. For example, when the number is
123454321, we could have a candidate of 123449999. It seems like a decent strategy is to take a monotone increasing prefix of N, then decrease the number before the "cliff" (the index where adjacent digits decrease for the first time) if it exists, and replace the rest of the characters with 9s.
When does that strategy fail? If
N = 333222, then our strategy would give us the candidate answer of 332999- but this isn't monotone increasing. However, since we are looking at all indexes before the original first occurrence of a cliff, the only place where a cliff could exist, is next to where we just decremented a digit.
Thus, we can repair our strategy, by successfully morphing our answer
332999 -> 329999 -> 299999 with a linear scan.
We'll find the first cliff
S[i-1] > S[i]. Then, while the cliff exists, we'll decrement the appropriate digit and move i back. Finally, we'll make the rest of the digits 9s and return our work.
We can prove our algorithm is correct because every time we encounter a cliff, the digit we decrement has to decrease by at least 1. Then, the largest possible selection for the rest of the digits is all nines, which is always going to be monotone increasing with respect to the other digits occurring earlier in the number.
- Time Complexity: , where is the number of digits in . Each step in the algorithm is a linear scan of the digits.
- Space Complexity: , the size of the answer.
public int monotoneIncreasingDigits(int N) {
char[] S = String.valueOf(N).toCharArray();
int i = 1;
while (i < S.length && S[i-1] <= S[i]) i++;
while (0 < i && i < S.length && S[i-1] > S[i]) S[--i]--;
for (int j = i+1; j < S.length; ++j) S[j] = '9';
return Integer.parseInt(String.valueOf(S));
}
https://leetcode.com/problems/monotone-increasing-digits/discuss/109792/easy-java
public int monotoneIncreasingDigits(int N) { char[] digit = (N + "").toCharArray(); int flag = digit.length; for (int i = digit.length - 1; i > 0; i--) { if (digit[i] < digit[i - 1]) { digit[i - 1]--; flag = i; } } Arrays.fill(digit, flag, digit.length, '9'); return Integer.parseInt(new String(digit)); }
public int monotoneIncreasingDigits2(int n) {
public int monotoneIncreasingDigits(int N) { char[] digit = (N + "").toCharArray(); int flag = digit.length; for (int i = digit.length - 1; i > 0; i--) { if (digit[i] < digit[i - 1]) { digit[i - 1]--; flag = i; } } Arrays.fill(digit, flag, digit.length, '9'); return Integer.parseInt(new String(digit)); }
public int monotoneIncreasingDigits2(int n) {
ArrayList<Integer> ints = toArray(n);
Optional<Integer> decreasingPoint = findDecreasingPoint(ints);
if (decreasingPoint.isPresent()) {
makeItLess(ints, decreasingPoint.get());
makeAll9s(ints, decreasingPoint.get() + 1);
}
int result = 0;
for (Integer i : ints) {
result = result * 10 + i;
}
return result;
}
// 1234, 125, 1111
private void makeItLess(ArrayList<Integer> ints, int decreasingPoint) {
if (decreasingPoint < 0)
return;
// case: 543
if (decreasingPoint == 0) {
makeItLessThan1(ints, decreasingPoint);
return;
}
// 125, 1234
if (ints.get(decreasingPoint) - 1 >= ints.get(decreasingPoint - 1)) {
makeItLessThan1(ints, decreasingPoint);
return;
}
// 1111, 1133-> 1129
ints.set(decreasingPoint, 9);
makeItLess(ints, decreasingPoint - 1);
}
private void makeItLessThan1(ArrayList<Integer> ints, int decreasingPoint) {
ints.set(decreasingPoint, ints.get(decreasingPoint) - 1);
}
private void makeAll9s(ArrayList<Integer> ints, int pos) {
while (pos < ints.size()) {
ints.set(pos, 9);
++pos;
}
}
private Optional<Integer> findDecreasingPoint(ArrayList<Integer> ints) {
for (int i = 0; i < ints.size(); i++) {
if (i - 1 >= 0 && ints.get(i) < ints.get(i - 1)) {
return Optional.of(i);
}
}
return Optional.empty();
}
private ArrayList<Integer> toArray(int n) {
Deque<Integer> result = new ArrayDeque<>();
while (n > 0) {
result.addFirst(n % 10);
n = n / 10;
}
return new ArrayList<Integer>(result);
}
Let's construct the answer digit by digit.
If the current answer is say,
123, and the next digit is 5, then the answer must be at least 123555...5, since the digits in the answer must be monotonically increasing. If this is larger than N, then it's impossible.
Algorithm
For each digit of
N, let's build the next digit of our answer ans. We'll find the smallest possible digit d such that ans + (d repeating) > N when comparing by string; that means d-1 must have satisfied ans + (d-1 repeating) <= N, and so we'll add d-1 to our answer. If we don't find such a digit, we can add a 9 instead.- Time Complexity: , where is the number of digits in . We do work building and comparing each candidate, and we do this times.
- Space Complexity: , the size of the answer and the temporary string we are comparing.
public int monotoneIncreasingDigits(int N) {
String S = String.valueOf(N);
String ans = "";
search: for (int i = 0; i < S.length(); ++i) {
for (char d = '1'; d <= '9'; ++d) {
if (S.compareTo(ans + repeat(d, S.length() - i)) < 0) {
ans += (char) (d - 1);
continue search;
}
}
ans += '9';
}
return Integer.parseInt(ans);
}
public String repeat(char c, int count) {
StringBuilder sb = new StringBuilder(count);
for (int i = 0; i < count; ++i) sb.append(c);
return sb.toString();
}
