这道题要是有想法,还是能解决的。
题目要求:大约num,但是是大于num中最小的。同时数字个数和num一样。(要增加的最少)
例如,654321,就不存在。
3245321,对于从后往前递增部分,不存在更大的,因此无法修改。
但是对于非递增部分,第一个 4, 是可以修订的部分,要修订为【5,3,2,1】中,第一个大于4的值,也就是5.然后将4,5交互,3254321,大于num了,但不是大于中最小的,5不能动,5之后的4321从排序,1234, 3241234就是最后的结果。
class Solution {
public:
bool isint(string num){
string maxnum = "2147483647";
if (num.size() == maxnum.size()){
if (num > maxnum){
return false;
}
else{
return true;
}
}
else if (num.size() < maxnum.size()){
return true;
}
else{
return false;
}
}
// 最小整数,和n数字相同,同时取值>n
//12345 => 12354
//12344 => 12434
int nextGreaterElement(int n) {
string num = to_string(n);
int jj = num.size()-2;
while(jj>=0&&num[jj]>=num[jj+1]){
jj --;
}
if (jj==-1){ // already max
return -1;
}
// find min >s[jj],must find
int ii = 0;
for(ii=num.size()-1;ii>=jj+1;ii--){
if (num[ii]>num[jj]){
break;
}
}
//swapii,jj
char ch = num[ii];
num[ii] = num[jj];
num[jj] = ch;
// sort [jj+1, end]
int start = jj+1;
int end = num.size()-1;
while(start<end){
char ch = num[start];
num[start] = num[end];
num[end] = ch;
start++;
end--;
}
if (isint(num)){
return atoi(num.c_str());
}
else{
return -1;
}
}
};