经典算法案例之下一个更大元素 III

我们先来看题目描述

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

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

示例 1 ：

输入：n = 12 输出：21

示例 2 ：

输入：n = 21 输出：-1

提示：

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

解决方案

方法：下一个排列

把 n 转换成字符串（字符数组），那么本题实际上是在求字符数组的 31. 下一个排列，当不存在下一个排列时返回 −1 。

代码

Python3

class Solution: def nextGreaterElement(self, n: int) -> int: nums = list(str(n)) i = len(nums) - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 if i < 0: return -1 j = len(nums) - 1 while j >= 0 and nums[i] >= nums[j]: j -= 1 nums[i], nums[j] = nums[j], nums[i] nums[i + 1:] = nums[i + 1:][::-1] ans = int(''.join(nums)) return ans if ans < 2 ** 31 else -1

C++

class Solution { public: int nextGreaterElement(int n) { auto nums = to_string(n); int i = (int) nums.length() - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i < 0) { return -1; } int j = nums.size() - 1; while (j >= 0 && nums[i] >= nums[j]) { j--; } swap(nums[i], nums[j]); reverse(nums.begin() + i + 1, nums.end()); long ans = stol(nums); return ans > INT_MAX ? -1 : ans; } };