专栏：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算法文档 。
热门跟贴