不一样的「下一个更大元素」

31. 下一个排列

556. 下一个更大元素 III

有一类题目是让我们求元素左边或者右边下一个更大的元素，这类题目需要用到单调栈，详情可见 单调栈

而今天的「下一个更大元素」题目是让我们重新排列数字，找到大于n的最小整数，和「下一个排列」很像，题目详情可见 下一个排列

下一个排列

题目详情可见 下一个排列

给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数。如123下一个更大的数为 132。如果没有更大的整数，则输出最小的整数

以 1,2,3 为例，其排列依次为：123 -> 132 -> 213 -> 231 -> 312 -> 321，该次序也符合从小到大的关系

算法推导

如何得到这样的排列顺序？这是本文的重点。我们可以这样来分析：

• 我们希望下一个数比当前数大，这样才满足「下一个排列」的定义。因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如123，将2和3交换就能得到一个更大的132

• 我们还希望下一个数增加的幅度尽可能的小，这样才满足「下一个排列与当前排列紧邻」的要求。为了满足这个要求，我们需要：

  • 在尽可能靠右的低位进行交换，需要从后向前查找
  • 将一个尽可能小的「大数」与前面的「小数」交换。比如123465，下一个排列应该把5和4交换而不是把6和4交换
  • 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。以123465为例：首先按照上一步，交换5和4，得到123564；然后需要将5之后的数重置为升序，得到123546。显然123546比123564更小，123546就是123465的下一个排列

以上就是求「下一个排列」的分析过程

可视化

以求12385764的下一个排列为例：

首先从后向前查找第一个相邻升序的元素对(i, j)。这里i = 4，j = 5，对应的值为5，7：

然后我们从j = 5; val = 7开始排序，如绿色部分所示：

在绿色部分中从小到大开始找第一个比i = 4; val = 5大的元素，并交换，即值5和6交换：

因此：12385764(橙色部分) 的下一个排列就是 12386457 (绿色部分)

算法实现

x
public void nextPermutation(int[] nums) {
    int n = nums.length;
    // 从后向前查找第一个相邻升序的元素对
    for (int i = n - 1; i > 0; i--) {
        if (nums[i] > nums[i - 1]) {
            // 从 i 开始排序
            Arrays.sort(nums, i, n);
            // 从 i 开始向后找第一个比 i - 1 大的元素
            for (int j = i; j < n; j++) {
                // 找到就交换
                if (nums[j] > nums[i - 1]) {
                    int temp = nums[j];
                    nums[j] = nums[i - 1];
                    nums[i - 1] = temp;
                    return ;
                }
            }
        }
    }
    // 不存在下一个排列更大的排列
    Arrays.sort(nums);
    return ;
}

下一个更大元素 III

题目详情可见 下一个更大元素 III

过程基本上和上个题目分析一致，完整代码如下：

x
public int nextGreaterElement(int n) {
    // 转换成 char[]
    char[] s = String.valueOf(n).toCharArray();
    // 从后向前查找第一个相邻升序的元素对
    for (int i = s.length - 1; i > 0; i--) {
        if (s[i] > s[i - 1]) {
            // 从 i 开始排序
            Arrays.sort(s, i, s.length);
            // 从 i 开始向后找第一个比 i - 1 大的元素
            for (int j = i; j < s.length; j++) {
                // 找到就交换
                if (s[j] > s[i - 1]) {
                    char t = s[i - 1];
                    s[i - 1] = s[j];
                    s[j] = t;
                    // 判断是否为 32 位整数
                    long ans = Long.parseLong(String.valueOf(s));
                    if (ans > Integer.MAX_VALUE) return -1;
                    return (int) ans;
                }
            }
        }
    }
    // 没有下一个更大的元素
    return -1;
}