LeetCode 0556. Next bigger element III - end of step 4

【LetMeFly】4 End of step ：556. Next bigger element III

Force button topic link ：https://leetcode.cn/problems/next-greater-element-iii/

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

Method 1 ： simulation

In fact, it is to find the next full permutation of the string corresponding to the number , And it's very simple （4 Step ）：

1. Looking back and forth , Find the first “ There is a number greater than it ” Number of numbers （ Write it down as s[i] = x）

2. stay s[i ~ Last ] Minimum greater than found in x Number of numbers （ Write it down as s[j] = y）

3. In exchange for s[i] and s[j]

4. stay s[i+1 ~ Last ] Sort the range from small to large

Then return the number corresponding to the string

• Time complexity $O(N^2)$, among $N$ Is the number of digits （$N\le 10$）
• Spatial complexity $O(N\log N)$, Spatial complexity is mainly caused by sorting

AC Code

C++

class Solution {
    
public:
    int nextGreaterElement(int n) {
    
        string s = to_string(n);
        bool changed = false;
        for (int i = s.size() - 2; i >= 0; i--) {
    
            char m = 58;  // '9' = 57
            int locm = i;
            for (int j = i + 1; j < s.size(); j++) {
    
                if (s[j] > s[i] && s[j] < m) {
    
                    m = s[j];
                    locm = j;
                }
            }
            if (locm != i) {
    
                changed = true;
                swap(s[i], s[locm]);
                sort(s.begin() + i + 1, s.end());
                break;
            }
        }
        if (!changed)
            return -1;
        ll ans = atoll(s.c_str());
        if (ans > INT_MAX)
            return -1;
        return ans;
    }
};

Make a little record hey

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125582351