给定一个32位正整数 n,你需要找到最小的32位整数,其与 n 中存在的位数完全相同,并且其值大于n。如果不存在这样的32位整数,则返回-1。
示例 1:
输入: 12
输出: 21
示例 2:
输入: 21
输出: -1
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/next-greater-element-iii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int nextGreaterElement(int number) {
string str = to_string(number);//转成字符串
if(str.size() <= 1)
return -1;//1位数,不存在
int n = str.size(), i, j;
bool found = false;
for(i = n-2; i >= 0; --i)//从倒数第二位开始比较,被交换数位
{
for(j = n-1; j > i; --j)
{
if(str[j] > str[i])
{
swap(str[i],str[j]);
found = true;
break;
}
}
if(found)
break;
}
if(!found)
return -1;
sort(str.begin()+i+1,str.end());//交换后,i位后面的排序
long num = 0;
for(i = 0; i < n; ++i)
num = num*10+str[i]-'0';//字符串转数字
if(num > INT_MAX)
return -1;
return num;
}
};
class Solution {
public:
int nextGreaterElement(int number) {
string str = to_string(number);
if(str.size() <= 1)
return -1;
int n = str.size(), i=n-2, j=n-1;
while(i >= 0 && str[i] >= str[i+1])
i--;//从后往前找到下降点
if(i == -1)
return -1;
while(j > i && str[j] <= str[i])
j--;//找到后面比交换点大的最小数
swap(str[i],str[j]);//交换i,j数位
i++; j=n-1;
while(i < j)
swap(str[i++],str[j--]);//i后面的排序(后面是降序的)
long num = 0;
for(i = 0; i < n; ++i)
num = num*10+str[i]-'0';
if(num > INT_MAX)
return -1;
return num;
}
};