1174. Next Greater Element III

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

Have you met this question in a real interview?  

Example

Example 1:

Input: 12
Output: 21

Example 2:

Input: 21
Output: -1

int nextGreaterElement(int n) { // Write your code here //这个思路是找到前面位置上的值比后面的小就交换。是不对的。以后这个不能把握的greedy解法尽量要再斟酌。 //后面还有两部逻辑，1是交换的不一定就是挨着的两个，后面位数上有更小的，需要用来交换 //2, 交换后，后面尾巴上的数要从小到大排序一次。另外，直接在int 数上操作太不方便了，这种数上的iteration，先转换成string方便 int copy = n; int d0 = n % 10; int d1 = 0; n /= 10; int cnt = 1; int flag = 0; while(n > 0){ d1 = n % 10; n /= 10; cnt++; if(d1 < d0){ flag = 1; break; } d0 = d1; } if(flag){ cnt -= 2; int multi = 1; while(cnt > 0){ multi *= 10; cnt--; } int leftOver = copy % multi; int modified = copy / multi; modified = (modified/100) * 100 + d0 * 10 + d1; return modified * multi + leftOver; } else{ return -1; } }

上面是开始写的不能通过的代码。下面是正确的
int nextGreaterElement(int num) { // Write your code here string s = to_string(num); int n = s.size(); int i; for(i = n - 1; i >= 1; i--){ if(s[i - 1] < s[i]){ break; } } if(i == 0){ return -1; } int j; for(j = n - 1; j >= i; j--){ //通过上一步的判断，在 i ~ n -1这个区间里的值都是递减的，
所以第一个遇到的比s[i -1]大的值，一定是大的里面最小的。很有意思！！ if(s[j] > s[i - 1]){ swap(s[j], s[i - 1]); break; } } sort(s.begin() + i, s.end()); //还要把尾巴处有小到大排序，保证是下一个大的里面最小的 long long res = stoll(s); return res > INT_MAX? -1 : res; }