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

Analysis

寻找next permutation，如果把全部permutation找出来是很耗时的，全排列需要O(n!)的时间和空间复杂度。因此需要一些比较特殊的处理。

Solution

和Next Permutation完全一样的步骤。

来自LeetCode Official 四段步骤处理：

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;
    }
}

By @sanketdige268

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/

https://leetcode.com/problems/next-greater-element-iii/discuss/101843/Java-Solution-like-Next-Permutation-Problem-O(n\