[daily question] 556 Next bigger element III

556. Next bigger element III
Medium question

Simple construction simulation problem .

• First pair x Every one of you takes out , Deposit nums Array （ The first element of the array is the original number x The lowest point of ）
• Try to find the first place that can be exchanged idx（ If you can't find , It indicates that there is no legal value , return −1）
  • from nums[0]（ original x The lowest point of ） Start looking for , Find the first 「 Descending 」 The location of idx
  • And then from [0,idx) Find a ratio in the range nums[idx] Exchange the largest decimal with it
  • From nums[0] Start looking for , Find the first satisfaction ratio nums[idx] Large number .
• When the exchange is completed , It's better than x 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 [0,idx) Still satisfied 「 Not strictly ascending 」 characteristic , Can be applied to it 「 Double pointer 」 Flip

class Solution {
    
    public int nextGreaterElement(int x) {
    
        List<Integer> nums = new ArrayList<>();
        // Take out x Every one of them 
        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;
    }
    // Exchange function 
    public void swap(List<Integer> nums, int a, int b) {
    
        int c = nums.get(a);
        nums.set(a, nums.get(b));
        nums.set(b, c);
    }
}

class Solution {
    
    public int nextGreaterElement(int n) {
    
        List<Integer> list = new ArrayList<>();
        // Take out n Every one of them 
        while (n > 0) {
    
            list.add(n % 10);
            n /= 10;
        }
        boolean flag = true;
        for (int i = 1; i < list.size(); i++) {
    
            // Find the position where the first high digit is less than the low digit , here [0,  High digit ) In ascending order 
            if (list.get(i - 1) > list.get(i)) {
    
                // Traverse from low to high , Find the first number greater than the high digit , Swap places 
                for (int j = 0; j < i; j++) {
    
                    if (list.get(j) > list.get(i)) {
    
                        swap(list, j, i);
                        break;
                    }
                }
                // here [0,  High position ) In ascending order , Flip this section , And modify the tag 
                for (int lo = 0, hi = i - 1; lo < hi; lo++, hi--) {
    
                    swap(list, lo, hi);
                }
                flag = false;
                break;
            }
        }
        // The number that meets the requirements is not found in the last cycle , be n There are no numbers that meet the meaning of the question , return -1
        if (flag) {
    
            return -1;
        }
        long sum = 0;
        // The result is greater than 2^31 - 1, return  -1
        for (int i = list.size() - 1; i >= 0; i--) {
    
            sum = sum * 10 + list.get(i);
            if (sum > Integer.MAX_VALUE) {
    
                return -1;
            }
        }
        return (int) sum;
    }
    // Exchange elements in the linked list 
    void swap(List<Integer> list, int lo, int hi) {
    
        int tmp = list.get(lo);
        list.set(lo, list.get(hi));
        list.set(hi, tmp);
    }
}