556. Next Greater Element III

题目:

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;
    }
};

上一篇:556,位运算解形成两个异或相等数组的三元组数目


下一篇:[LeetCode] 556. Next Greater Element III