题目:
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 1:
Input: n = 12 Output: 21
Example 2:
Input: n = 21 Output: -1
Constraints:
1 <= n <= 2^31 - 1
思路1:
这题第一反应直接偷懒,先转成string,或者vector也行,不过string转换更方便点,然后用next_permutation函数找出下一个排列,用stol转回long long,这里要转long long是因为结果可能会大于int,如果转给int很可能报错的。如果答案大于int返回-1,否则返回答案即可。
代码1:
class Solution {
public:
int nextGreaterElement(int n) {
string s=to_string(n);
if(!next_permutation(s.begin(),s.end()))
return -1;
long long ans=stol(s);
if(ans>INT_MAX)
return -1;
return ans;
}
};
思路2:
然后好好做观察规律的话,以123459876为例,首先我们要找到从后面数第一个降序的数,1234(59876),即5。然后reverse他后面的数字,变成12345(6789)。reverse以后找到5之后的第一个比它大的数字直接swap一下即可。这里还是要注意几个点,首先还是要转string,好操作,并且如果size为1则直接返回-1,因为不可能再排列了;最后还是要记得用long long和INT_MAX去比较。
代码2:
class Solution {
public:
int nextGreaterElement(int n) {
string s= to_string(n);
if(s.size()==1)
return -1;
int i=s.size()-2;
for(;i>=0;i--)
{
if(s[i]<s[i+1])
break;
}
if(i==-1)
return -1;
reverse(s.begin()+i+1,s.end());
for(int j=i+1;j<s.size();j++)
{
if(s[j]>s[i])
{
swap(s[j],s[i]);
break;
}
}
long long ans=stol(s);
return ans>INT_MAX?-1:ans;
}
};