Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.
Example 1:
Input: 12
Output: 21
Example 2:
Input: 21
Output: -1
Solution:
class Solution {
public int nextGreaterElement(int n) {
// 1 2 5 3 3 0
// j k
// 1 3 5 2 3 0
// 1 3 0 2 3 5
// find largest j such that a[j] < a[j + 1]
// find smallest element k such that a[k] > a[j]
// swap j k
// sort a[j + 1:]
char[] arr = Integer.toString(n).toCharArray();
int j = -1, k = -1;
for (int i = arr.length - 2; i >= 0; i --) {
if (arr[i] < arr[i + 1]) {
j = i;
break;
}
}
if (j == -1) return -1;
for (int i = j + 1; i < arr.length; i ++) {
if (arr[i] > arr[j] && (k == -1 || arr[i] < arr[k])) {
k = i;
}
}
swap(arr, j, k);
Arrays.sort(arr, j + 1, arr.length);
String greater = new String(arr);
if (Long.parseLong(greater) > Integer.MAX_VALUE) return -1;
return Integer.parseInt(greater);
}
private void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}