Leetcode 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 <= 231 - 1

Problem Analysis:

If n < 10 then there is only one digit in the integer n, so it don’t exist greater value with same digits.

Others, we assume n has k digits. we iterate the digits from back to front to find same j = i + 1 ≤ k, and digit[i] < digit[j]. Then if we swap the two digit, it is a greater value with same digits.

But it may not be the smallest one. As digit[i] maybe < digit[m], where j < m < k. So we iterate from j + 1 to k to find same m, that as j < o ≤ m, digit[o] ≤ digit[j], and m < p ≤ k, digit[p] > digit[j]. Then we swap digit[i] and digit[m], then from j to k, the digits are monotonically decreasing. Then we reverse the digits from j to k, we get the smallest value with same digits.

in STL, the next_permutation function also works.

Solution

class Solution {
public:
    int nextGreaterElement(int n) {
        if (n < 10) return -1;
        vector<int> digits;
        while (n > 0) {
            digits.push_back(n % 10);
            n /= 10;
        }
        reverse(digits.begin(), digits.end());
        int next{(int)digits.size() - 1};
        while (true) {
            int current{next};
            if (digits[--next] < digits[current]) {
                int middle{(int)digits.size()};
                do {
                    --middle;
                } while (digits[next] >= digits[middle]);
                swap(digits[middle], digits[next]);
                reverse(digits.begin() + current, digits.end());
                break;
            }
            if (next == 0) {
                return -1;
            }
        }
        long long res{0LL};
        for (int i = 0; i < digits.size(); ++i)
            res = res * 10 + digits[i];
        return (res > numeric_limits<int>::max()) ? -1 : res;
    }
};

time complexity is O(digits)

Space complexity is O(digits)