# Next Greater Element III

Medium

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 integernand 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

Next Permutation完全一样的步骤。

1. 从右往左搜索到第一个 `a[i] > a[i - 1]`
2. `a[i]`的右侧搜索比`a[i - 1]`大的最小的数`a[j]`
3. 交换`a[ i - 1]`, `a[j]`
4. 排序从`i`到末尾（nums.length）的数字，按照升序
``````public class Solution {
public int nextGreaterElement(int n) {
char[] a = ("" + n).toCharArray();
int i = a.length - 2;
while (i >= 0 && a[i + 1] <= a[i]) {
i--;
}
if (i < 0)
return -1;
int j = a.length - 1;
while (j >= 0 && a[j] <= a[i]) {
j--;
}
swap(a, i, j);
reverse(a, i + 1);
try {
return Integer.parseInt(new String(a));
} catch (Exception e) {
return -1;
}
}
private void reverse(char[] a, int start) {
int i = start, j = a.length - 1;
while (i < j) {
swap(a, i, j);
i++;
j--;
}
}
private void swap(char[] a, int i, int j) {
char temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
``````
``````public class Solution {
public int nextGreaterElement(int n) {
char[] number = (n + "").toCharArray();

int i, j;
// I) Start from the right most digit and
// find the first digit that is
// smaller than the digit next to it.
for (i = number.length-1; i > 0; i--)
if (number[i-1] < number[i])
break;

// If no such digit is found, its the edge case 1.
if (i == 0)
return -1;

// II) Find the smallest digit on right side of (i-1)'th
// digit that is greater than number[i-1]
int x = number[i-1], smallest = i;
for (j = i+1; j < number.length; j++)
if (number[j] > x && number[j] <= number[smallest])
smallest = j;

// III) Swap the above found smallest digit with
// number[i-1]
char temp = number[i-1];
number[i-1] = number[smallest];
number[smallest] = temp;

// IV) Sort the digits after (i-1) in ascending order
Arrays.sort(number, i, number.length);

long val = Long.parseLong(new String(number));
return (val <= Integer.MAX_VALUE) ? (int) val : -1;
}
}
``````

## Reference

https://leetcode.com/problems/next-greater-element-iii/solution/