556 Next Greater Element III 下一個(gè)更大元素 III
Description:
Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.
Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.
Example:
Example 1:
Input: n = 12
Output: 21
Example 2:
Input: n = 21
Output: -1
Constraints:
1 <= n <= 2^31 - 1
題目描述:
給你一個(gè)正整數(shù) n 肤视，請(qǐng)你找出符合條件的最小整數(shù)疗涉，其由重新排列 n 中存在的每位數(shù)字組成，并且其值大于 n 立宜。如果不存在這樣的正整數(shù)穴翩，則返回 -1 探赫。
注意 厦画，返回的整數(shù)應(yīng)當(dāng)是一個(gè) 32 位整數(shù) 牍陌，如果存在滿足題意的答案擎浴，但不是 32 位整數(shù) ，同樣返回 -1 毒涧。
示例 :
示例 1：
輸入：n = 12
輸出：21
示例 2：
輸入：n = 21
輸出：-1
提示:
1 <= n <= 2^31 - 1
思路:
參考LeetCode #31 Next Permutation 下一個(gè)排列
從后往前找到第一個(gè)逆序的數(shù)對(duì)
交換之后將逆序數(shù)對(duì)之后的元素逆序
時(shí)間復(fù)雜度 O(n), 空間復(fù)雜度 O(n)
代碼:
C++:
class Solution
{
public:
int nextGreaterElement(int n)
{
string str = to_string(n);
next_permutation(str.begin(), str.end());
long num = stol(str);
return num > INT_MAX or num <= n ? -1 : num;
}
};
Java:
class Solution {
public int nextGreaterElement(int n) {
char[] nums = ("" + n).toCharArray();
int i = nums.length - 2, j = nums.length - 1;
while (i >= 0 && nums[i + 1] <= nums[i]) --i;
if (i < 0) return -1;
while (j >= 0 && nums[j] <= nums[i]) --j;
swap(nums, i, j);
reverse(nums, i + 1);
try {
return Integer.parseInt(new String(nums));
} catch (Exception e) {
return -1;
}
}
private void reverse(char[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) swap(nums, i++, j--);
}
private void swap(char[] nums, int i, int j) {
char temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
Python:
class Solution:
def nextGreaterElement(self, n: int) -> int:
nums, m = [x for x in str(n)], len(str(n))
for i in range(m - 2, -1, -1):
if nums[i] < nums[i + 1]:
for j in range(m - 1, i, -1):
if nums[j] > nums[i]:
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1:] = nums[i + 1:][::-1]
break
break
return result if (result := int(''.join(nums))) < 2 ** 31 and result != n else -1
