c++ easy-to-follow solution without converting to string or using next_permutation.


  • 0
    Q
    class Solution {
    public:
        int nextGreaterElement(int n) {
            long long m=n;
            int last=0;
            int power1=1;
            int reversed=0;
            while(m && (m%10)>=last )
            {
                last=m%10;
                reversed=10*reversed+last;
                m/=10;
                power1*=10;
            }
            
            if(m==0) return -1;
            
            int firstDigit=m%10;
            
            //find second digit, power2 can not be zero;
            int tmp=reversed;
            int power2=power1/10;
            while(tmp/power2<=firstDigit)
            {
                tmp%=power2;
                power2/=10;
            }
            int secondDigit=tmp/power2;
            
            //swap firstDigit and secondDigit;
            reversed=reversed-secondDigit*power2+firstDigit*power2;
            m=(m+secondDigit-firstDigit)*power1+reversed;
            
            if(m>INT_MAX) return -1;
            
            return m;
            
            
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.