556. Next Greater Element III

T: O(n)
S: O(n)

```java
class Solution {
    public int nextGreaterElement(int n) {
        String s = String.valueOf(n);
        int pivot = findPivot(s);
        //System.out.println(pivot);

        if (pivot == -1) {
            return -1;
        }
        int swapTargetIdx = findMaxNumberAfterPivot(s, pivot);
        //System.out.println(swapTargetIdx);

        char[] cAry = s.toCharArray();
        swap(cAry, pivot, swapTargetIdx);
        reverse(cAry, pivot+1);

        //System.out.println(String.valueOf(cAry));
        long result = Long.parseLong(String.valueOf(cAry));
        return (result <= Integer.MAX_VALUE) ? (int)result : -1;
    }
    private int findPivot(String s) {
        int n = s.length();
        for (int i = n -1; i >= 1; i--) {
            if (s.charAt(i) > s.charAt(i-1)) {
                return i-1;
            }
        }
        return -1;
    }
    private int findMaxNumberAfterPivot(String s, int pivot) {
        int n = s.length();
        for (int i = n -1; i > pivot; i--) {
            if (s.charAt(i) > s.charAt(pivot)) {
                return i; // find first larger than pivot, -> it's the > pivot and smaller one
            }
        }
        return -1;
    }
    private void swap(char[] cAry, int i, int j) {
        char temp = cAry[i];
        cAry[i] = cAry[j];
        cAry[j] = temp;
    }
    private void reverse(char[] cAry, int start) {
        int left = start;
        int right = cAry.length-1;
        while (left < right) {
            swap(cAry, left, right);
            left++;
            right--;
        }
    }
}


/***
T: O(n)
S: O(n)


4321
-> -1
from end to start is incresing -> -1
 
 x
2341
from end to start
if we can find increasing -> then decresing one...
so it is pivot = 3

3, then find first > 3 in 41, find 4

        
swap 2 43 1
at last sort after this pivot (p+1, end)


another ex:
       x 
2147483476

pivot = 4

find first one. > pivot = 4 -> it's 6

so swap 4 and 6
       x 
2147483674
then after pivot -> do reverse ->  (why reverse? 
因為一開始找 pivot...找到 pivot 時, 後面都是從後面往前遞增, 所以 reverse it, 就會是最小的

then it's the next greater

2147483647
 */
```