LeetCode 556. Next Greater Element III

Problem

LeetCode 556. Next Greater Element III

1. 题目简述

给出一个32-bit的正整数，找出由它的每一位组成的下一个比它大一点的数字，如果当前已经是最大或者没有一个32位的int值可以表示，则返回-1。例如：

Example 1:

Input: 12
Output: 21


Example 2:

Input: 21
Output: -1

2. 算法思路

相关问题：

1. LeetCode 496. Next Greater Element I
2. LeetCode 556. Next Greater Element III
3. LeetCode 31. Next Permutation

全排列

这道题其实和LeetCode 130. Surrounded Regions的单调栈没有任何关系，反而是和LeetCode 31. Next Permutation一模一样，目的就是找出下一个更大的数字，其难点在于注意integer的max值，如果变换后值超出int1的范围，则返回-1.

具体思路见：LeetCode 31. Next Permutation

class Solution {
    public int nextGreaterElement(int n) {
        // 我觉得这里更多需要注意的是32位整形的这个约束条件，为了不溢出，我们需要将其转化为long类型
        // 和next permutation一样的做法，从后向前找第一个降序数字x，如果找不到，说明不行；例如12386，我们找到的就是8；
        // 然后我们从x(包括x)的右侧找到第一个比“3”大的数字，也就是6，交换它们；
        // 数字变成12683，然后将x及x的右侧降序排列
        // 比较其和intMax的大小，如果更大，则还是返回-1。
        long intMax = Integer.MAX_VALUE;
        List<Integer> digitsList = new ArrayList();
        int num = n;

        // 计算数字各个位，存起来转化成数组，方便计算；从低位到高位存。
        while (num > 0) {
            digitsList.add(num % 10);
            num /= 10;
        }
        int length = digitsList.size();
        int[] digits = new int[length];
        for (int i = 0; i < length; i++) {
            digits[i] = digitsList.get(length - i - 1);
        }

        // 从后向前找第一个降序的数字
        int pos = -1;
        for (int i = length - 1; i > 0; i--) {
            if (digits[i] > digits[i - 1]) {
                pos = i;
                break;
            }
        }
        if (pos == -1) {
            return -1;
        }

        // 从后向前找第一个比digits[pos - 1]大的数字，交换它们，这个数字一定存在，最坏情况不过是pos这个数
        for (int i = length - 1; i >= pos; i--) {
            if (digits[i] > digits[pos - 1]) {
                int temp = digits[pos - 1];
                digits[pos - 1] = digits[i];
                digits[i] = temp;
                break;
            }
        }

        // 重新排列从pos到末尾的数字，但是我们知道它们都是降序的，首尾pointer交换
        int start = pos, end = length - 1;
        while (start < end) {
            int temp = digits[start];
            digits[start] = digits[end];
            digits[end] = temp;
            start++;
            end--;
        }

        // 将重新生成的数字用long看一下是否越界了
        long newNum = 0;
        long multiplier = 1;
        for (int i = length - 1; i >= 0; i--) {
            newNum += multiplier * digits[i];
            multiplier *= 10;
        }

        if (newNum > intMax) {
            return -1;
        } else {
            return (int)newNum;
        }
    }
}