小米今年招了4000名应届生，用10年的时间让其佼佼者成为技术专家或总经理。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

本周三小米举办2024届小米应届生迎新典礼，小米CEO雷军出席典礼并发表演讲。据雷军介绍，2024年小米一共招募了4000名应届生，明年至少还会招募4000-5000名。

小米“应届生计划”的目标就是10年时间让其中的佼佼者成为技术专家，或者成为总经理。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第556题：下一个更大元素 III。

问题描述

来源：LeetCode第556题

难度：中等

给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

示例1：

输入：n = 12 输出：21

示例2：

输入：n = 21 输出：-1

• 1 <= n <= 2^31 - 1

问题分析

这题和前面讲的 基本完全一样，都是求下一个更大的值，只不过他们给的参数不一样，前面那道题直接给了一个数组，而这题是给了一个数字。但不影响，我们可以先把数字中的每一位都提取出来，构成一个数组，那么这题就和前面那道题完全一样了。具体实现原理可以参考前面的，这里就不在重复介绍。

JAVA：

public int nextGreaterElement(int n) {
    String str = String.valueOf(n);
    int[] nums = new int[str.length()];
    // 把数字 n 的每一位转成数组
    for (int i = 0; i < str.length(); i++)
        nums[i] = str.charAt(i) - '0';
    // 如果不存在下一个，返回 -1 。
    if (!nextPermutation(nums))
        return -1;
    // 把数组转化为数字
    long ans = 0;
    for (int num : nums) {
        ans = ans * 10 + num;
        if (ans > Integer.MAX_VALUE)
            return -1;
    }
    return (int) ans;
}

public boolean nextPermutation(int[] nums) {
    int left = nums.length - 2;
    // 两两比较，从后面往前找第一个降序的
    while (left >= 0 && nums[left] >= nums[left + 1])
        left--;
    // 如果都是逆序的，也就是没有下一个更大的元素。
    if (left < 0)
        return false;
    int right = nums.length - 1;
    // 从后面查找第一个比nums[left]大的值
    while (nums[right] <= nums[left])
        right--;
    swap(nums, left, right);
    // 反转后面升序的数字
    reverse(nums, left + 1, nums.length - 1);
    return true;
}

// 反转子数组[left，right]中的元素
private void reverse(int[] nums, int left, int right) {
    while (left < right)
        swap(nums, left++, right--);
}

// 交换数组中的两个数字
private void swap(int[] nums, int left, int right) {
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
}

C++：

public:
    int nextGreaterElement(int n) {
        vector

  nums;         while (n != 0) {             nums.push_back(n % 10);             n /= 10;         }         reverse(nums.begin(), nums.end());         // 如果不存在下一个，返回 -1 。         if (!nextPermutation(nums))             return -1;         // 把数组转化为数字         long ans = 0;         for (int num: nums) {             ans = ans * 10 + num;             if (ans > INT_MAX)                 return -1;         }         return (int) ans;     }     bool nextPermutation(vector

  &nums) {         int left = nums.size() - 2;         // 两两比较，从后面往前找第一个降序的         while (left >= 0 && nums[left] >= nums[left + 1])             left--;         // 如果都是逆序的，也就是没有下一个更大的元素。         if (left < 0)             return false;         int right = nums.size() - 1;         // 从后面查找第一个比nums[left]大的值         while (nums[right] <= nums[left])             right--;         swap(nums[left], nums[right]);         // 反转后面升序的数字         reverse(nums.begin() + left + 1, nums.end());         return true;     }

Python：

def nextGreaterElement(self, n: int) -> int:
    nums = []
    while n != 0:
        nums.append(n % 10)
        n //= 10
    nums.reverse()  # 反转列表，使其从高位到低位
    # 如果不存在下一个更大的排列，返回 -1
    if not self.next_permutation(nums):
        return -1
        # 把列表转化为数字，同时检查是否超出int的范围
    ans = 0
    INT_MAX = 2 ** 31 - 1  # 模拟C++的INT_MAX
    for num in nums:
        ans = ans * 10 + num
        if ans > INT_MAX:
            return -1
    return ans

def next_permutation(self, nums: list[int]) -> bool:
    left = len(nums) - 2
    # 从后往前找第一个降序的位置
    while left >= 0 and nums[left] >= nums[left + 1]:
        left -= 1
        # 如果整个列表都是降序的，则没有下一个更大的排列
    if left < 0:
        return False
    right = len(nums) - 1
    # 从后往前找第一个比nums[left]大的数
    while nums[right] <= nums[left]:
        right -= 1
        # 交换nums[left]和nums[right]
    nums[left], nums[right] = nums[right], nums[left]
    # 反转left+1及其之后的部分
    nums[left + 1:] = reversed(nums[left + 1:])
    return True

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。