556. The next larger element III: simple construction simulation questions

Title Description

This is a LeetCode Upper 556. Next bigger element III , The difficulty is secondary .

Tag : 「 simulation 」、「 Double pointer 」

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

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

Example 1：

 Input ：n = 12

 Output ：21

Example 2：

 Input ：n = 21

 Output ：-1

Tips ：

simulation

According to the meaning , Only given numbers Itself from high to low is 「 Not strictly descending 」 when , We can't find a legal value .

First , We can do it first Take it out, everyone , Deposit nums Array （ The first element of the array is the original number The lowest point of ）.

Then try to find the first place to exchange idx（ If you can't find , It indicates that there is no legal value , return ）, From （ original The lowest point of ） Start looking for , Find the first 「 Descending 」 The location of idx, And then from Find a ratio in the range Exchange the largest decimal with it , Also from the Start looking for , Find the first satisfaction ratio Large number .

When the exchange is completed , It's better than The goal of becoming bigger has been achieved by idx Bit by bit （ Subsequent sorting should be arranged from small to large ）, At the same time, after the exchange Still satisfied 「 Not strictly ascending 」 characteristic , So we can apply it 「 Double pointer 」 Flip .

Code ：

class Solution {
    public int nextGreaterElement(int x) {
        List<Integer> nums = new ArrayList<>();
        while (x != 0) {
            nums.add(x % 10);
            x /= 10;
        }
        int n = nums.size(), idx = -1;
        for (int i = 0; i < n - 1 && idx == -1; i++) {
            if (nums.get(i + 1) < nums.get(i)) idx = i + 1;
        }
        if (idx == -1) return -1;
        for (int i = 0; i < idx; i++) {
            if (nums.get(i) > nums.get(idx)) {
                swap(nums, i, idx);
                break;
            }
        }
        for (int l = 0, r = idx - 1; l < r; l++, r--) swap(nums, l, r);
        long ans = 0;
        for (int i = n - 1; i >= 0; i--) ans = ans * 10 + nums.get(i);
        return ans > Integer.MAX_VALUE ? -1 : (int)ans;
    }
    void swap(List<Integer> nums, int a, int b) {
        int c = nums.get(a);
        nums.set(a, nums.get(b));
        nums.set(b, c);
    }
}

• Time complexity ：
• Spatial complexity ：

Last

This is us. 「 Brush through LeetCode」 The first of the series No.556 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .