[LeetCode] Problem 556 - Next Greater Element III

Posted on | In ,

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

No.1

Input: 12

Output: 21

No.2

Input: 21

Output: -1

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public int nextGreaterElement(int n) {
    char[] ch = String.valueOf(n).toCharArray();
    int i = ch.length - 2;

    while (i >= 0 && ch[i] >= ch[i + 1])
        i--;

    if (i < 0)
        return -1;

    int j = ch.length - 1;

    while (j >= i && ch[j] <= ch[i])
        j--;

    swap(ch, i, j);

    reverse(ch, i + 1, ch.length - 1);

    long result = Long.parseLong(String.valueOf(ch));
    return result > Integer.MAX_VALUE ? -1 : (int) result;
}

private void swap(char[] ch, int i, int j) {
    char temp = ch[i];
    ch[i] = ch[j];
    ch[j] = temp;
}

private void reverse(char[] ch, int i, int j) {
    while (i < j) {
        swap(ch, i, j);
        i++;
        j--;
    }
}