力扣 556. 下一个更大元素 III

题目来源：https://leetcode.cn/problems/next-greater-element-iii/

大致题意：
给一个32位的整数，返回将整数各位数字重新排列后能组成大于原整数的最小值，如果不存在这样的最小值，则返回 -1

思路

假设整数中有高位数为 i ，低位数为 j，如果 i < j，那么交换 i 和 j 就一定得到大于原整数的值

如果遍历整数每一位的值，很容易找到满足低位数值大于高位数值的情况，难点在于交换后的值是不是大于原整数的最小值

已知交换大于高位数值的低位数值后，一定会使整数值更大，那么交换的位数越低，增加的数值也就越小。比如千位和百位的值都小于个位数的值，将个位数与百位数交换得到的值一定小于将个位数与千位数交换的值 （3486，交换个位与百位得到 3684，交换个位与千位得到 6483）

于是可以从低位遍历到高位，当遍历到首个高位数小于低位数时进行交换。那么应该注意到，如上述例子 3486，在遍历到百位时，百位小于十位，如果将这两位交换的值为 3846，要小于百位与个位交换。所以实际交换时，应该使用大于当前高位值的最小数与其交换。同时，由于在遍历到该高位之前，遇到的数都是递增的（否则在遍历到该位之前就会出现高位小于低位的情况），所以可以直接从末尾遍历求得第一个大于该位的值即为最小的大于该位的值

但是此时交换后的值仍可能不是所有数位全排列后的大于原值的最小值，比如 2302431，按照上述规则找到并交换后的值为 2303421，但是最小值应该是 2303412。

可见，在上述例子中，变化的是与高位交换位置到最低位的数字，首先可以知道在高位的值更大以后，低位的值哪怕都为 0 也比之前的大，所以应该尽量降低低位的值，那么在遍历时与高位交换的位置到最低位都满足递增关系，于是可以直接将这一段数字反转得到最小值

所以解题思路可以概括为

1. 遍历数字，存下每一位的值
2. 从低位向高位遍历，如果遍历到当前位的值小于上一位，那么从低位开始遍历找到第一个大于当前位的值，然后将两个值交换，并退出循环；否则继续遍历，直至数字遍历结束
3. 判断数字遍历指针是否结束，若结束表明未交换，直接返回 -1
4. 反转交换位置到最低位的数字
5. 获取交换后的数字
6. 判断交换后数字与原数字的大小关系，如果交换后数字小于原数字（表示出现了越界）则返回 -1，否则返回交换后数字

class Solution {
    public int nextGreaterElement(int n) {
        // 存原数字
        int pre = n;
        StringBuffer sb = new StringBuffer();
        // 获取每一位的值
        while (n > 0) {
            sb.append(n % 10);
            n /= 10;
        }
        char[] nums = sb.toString().toCharArray();
        int len = nums.length;
        int idx = 1;
        // 遍历查找交换位置
        while (idx < len) {
            // 当前位对应值小于上一位
            if (nums[idx] < nums[idx - 1]) {
                // 在低位中找最小的大于当前位的值
                int j = 0;
                while (nums[j] <= nums[idx]) {
                    j++;
                }
                // 交换
                swap(nums, idx, j);
                break;
            }
            idx++;
        }
        // 判断是否交换过
        if (idx == len) {
            return -1;
        }
        // 反转低位数字
        reverse(nums, 0, idx - 1);
        int ans = 0;
        // 获取交换后的值
        for (int i = len - 1; i >= 0; i--) {
            ans = ans * 10 + nums[i] - '0';
        }
        // 判断是否越界
        return ans <= pre ? -1 : ans;
    }

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

    public void reverse(char[] strs, int l, int r) {
        while (l < r) {
            swap(strs, l++, r--);
        }
    }
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55