给定一个32位正整数 n,你需要找到最小的32位整数,其与 n 中存在的位数完全相同,并且其值大于n。如果不存在这样的32位整数,则返回-1。
示例 1:
输入: 12 输出: 21
示例 2:
输入: 21 输出: -1
题解:按数字的性质,从低位到高位遍历,到达某一位时,再从低位中找到可以交换后变大的数字即可,然后这一位到个位的数字全部排序,让数字尽可能小。另外注意题目要求的是在32位数据范围内,注意特判。
AC代码
class Solution { public: struct Node { int val; int pos; bool operator<(const Node&a)const { return a.val>val; } }; priority_queue<Node>pt; static int cmp(int a,int b) { return a>b; } int nextGreaterElement(int n) { if(n==0)return -1; vector<int>q; while(n>0) { q.push_back(n%10); n/=10; } bool flag=true; for(int i=1;i<q.size();i++) { if(q[i-1]>q[i]) { flag=false; break; } } if(flag)return -1; Node t; t.pos=0,t.val=q[0]; pt.push(t); int sign; for(int i=1;i<q.size();i++) { if(pt.top().val>q[i]) { Node w; while(pt.empty()==false&&pt.top().val>q[i]) { w=pt.top(); pt.pop(); } swap(q[w.pos],q[i]); sign=i; break; } else { t.pos=i; t.val=q[i]; pt.push(t); } } sort(q.begin(),q.begin()+sign,cmp); long long ans=0; for(int i=q.size()-1;i>=0;i--) { ans*=10; ans+=q[i]; } if(ans>2e9)return -1; return ans; } };