C++ simple solution, O(logN)

  • 0

    This is a variation of "Next Permutation Problem".

    1. convert integer n to string s.
    2. find the increasing sequence from right to left, use i to denote the position of first decreasing digit. If i<0, no larger number, return -1;
    3. find the first number that is larger than s[i], use j to denote the position.
    4. swap s[i] and s[j].
    5. reverse the sub string from s[i+1] to the end;
    6. check the result if it is over the integer's upper limit.
        int nextGreaterElement(int n) {
            string s = to_string(n);
            if (s.size()==1) return -1;
            int i =s.size()-2;
            while (i>=0 && s[i]>=s[i+1]) i--;
            if (i<0) return -1;
            int j = s.size()-1;
            while (j>i && s[j]<=s[i]) j--;
            swap(s[i], s[j]);
            reverse(s.begin()+i+1, s.end());
            long res = stol(s);
            return res > 0x7FFFFFFF? -1:(int)res;

Log in to reply

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