556. Next Greater Element III

class Solution {
    public int nextGreaterElement(int n) {
        // arr = [1,2,5,3] 的下一个排列是 [1,3,2,5]

        char[] chars = String.valueOf(n).toCharArray();

        int leftIndex = -1;
        for (int i = chars.length - 2; i >= 0; i--) {
            if (chars[i] < chars[i + 1]) {
                // 找到了一个上升趋势
                leftIndex = i;
                break;
            }
        }

        if (leftIndex == -1) {
            return -1;
        }

        // 存在上升趋势的情况下，即右侧存在更大元素，此时在右侧寻找大于 nums[leftIndex] 的最小元素，即使上升趋势最小
        for (int i = chars.length - 1; i > leftIndex; i--) {
            if (chars[i] > chars[leftIndex]) {
                swap(chars, i, leftIndex);
                break;
            }
        }

        reverse(chars, leftIndex + 1, chars.length - 1);

        int res = 0;
        // 注意数组转整数是正向遍历
        for (int i = 0; i < chars.length; i++) {
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && chars[i] > '7')) {
                return -1;
            }
            res = res * 10 + (chars[i] - '0');
        }
        return res;
    }

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

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

References

556. Next Greater Element III