[556. Next larger element III]

source ： Power button （LeetCode）

describe ：

Give you a positive integer n , Please find the smallest integer that meets the conditions , It consists of rearranging n Each number present in the consists of , And its value is greater than n . If there is no such positive integer , Then return to -1 .

Be careful , The returned integer should be a 32 An integer , If there is an answer that satisfies the meaning of the question , But it's not 32 An integer , Also return to -1 .

Example 1：

 Input ：n = 12
 Output ：21

Example 2：

 Input ：n = 21
 Output ：-1

Tips ：

1 <= n <= 2³¹ - 1

Method 1 ： Next spread

hold n Convert to string （ A character array ）, So this problem is actually solving the character array Next spread , Return when there is no next spread −1.

Code ：

class Solution {
    
public:
    int nextGreaterElement(int n) {
    
        auto nums = to_string(n);
        int i = (int) nums.length() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
    
            i--;
        }
        if (i < 0) {
    
            return -1;
        }

        int j = nums.size() - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
    
            j--;
        }
        swap(nums[i], nums[j]);
        reverse(nums.begin() + i + 1, nums.end());
        long ans = stol(nums);
        return ans > INT_MAX ? -1 : ans;
    }
};

Execution time ：0 ms, In all C++ Defeated in submission 100.00% Users of
Memory consumption ：5.8 MB, In all C++ Defeated in submission 57.91% Users of
Complexity analysis
Time complexity ： O(logn).
Spatial complexity ：O O(logn).

Method 2 ： mathematics

Do not convert to character array , How to use O(1) Space complexity to solve this problem ？

If not required 64 Bit integer ？

Similar method I , We from n Start , Constantly compare the size of the lowest digit and the second lowest digit , If the next lowest digit is not lower than the lowest digit , Then remove the lowest digit , Continue to cycle . At the end of the cycle n It corresponds to the subscript of method one i, namely nums Before i + 1 Characters .

For method one, the subscript j The same is true for the calculation of .

Code ：

class Solution {
    
public:
    int nextGreaterElement(int n) {
    
        int x = n, cnt = 1;
        for (; x >= 10 && x / 10 % 10 >= x % 10; x /= 10) {
    
            ++cnt;
        }
        x /= 10;
        if (x == 0) {
    
            return -1;
        }

        int targetDigit = x % 10;
        int x2 = n, cnt2 = 0;
        for (; x2 % 10 <= targetDigit; x2 /= 10) {
    
            ++cnt2;
        }
        x += x2 % 10 - targetDigit; //  hold  x2 % 10  Switch to  targetDigit  On 

        for (int i = 0; i < cnt; ++i, n /= 10) {
     //  reverse  n  Last  cnt  Spell the numbers to  x  after 
            int d = i != cnt2 ? n % 10 : targetDigit;
            if (x > INT_MAX / 10 || x == INT_MAX / 10 && d > 7) {
    
                return -1;
            }
            x = x * 10 + d;
        }
        return x;
    }
};

Execution time ：0 ms, In all C++ Defeated in submission 100.00% Users of
Memory consumption ：5.7 MB, In all C++ Defeated in submission 94.76% Users of
Complexity analysis
Time complexity ： O(logn).
Spatial complexity ： O(1). We just need a constant space to hold a few variables .
author：LeetCode-Solution