0556. Next Greater Element III

https://leetcode.com/problems/next-greater-element-iii

Description

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

ac

so many anoying boundary check

class Solution {
    public int nextGreaterElement(int n) {
        // edge cases
        if (n <= 10) return -1;

        List<Integer> list = new ArrayList<>();
        int exchange = -1;
        while (n > 0) {
            int curr = n % 10;
            n /= 10;
            if (list.size() != 0 && curr < list.get(list.size() - 1)) {
                int i = list.size() - 1;
                while (i >= 0 && curr < list.get(i)) i--;
                exchange = list.get(i+1);
                list.set(i+1, curr);
                break;
            } else {
                list.add(curr);
            }
        }

        if (n == 0 && exchange == -1) return -1;  // cannot find result

        n = n * 10 + exchange;
        for (int i : list) {
            if (n > Integer.MAX_VALUE / 10 || n == Integer.MAX_VALUE / 10 && i > 8) 
                return -1;  // out of boundary
            n = n * 10 + i;
        }

        return n;
    }
}

class Solution {
    public int nextGreaterElement(int n) {
        // edge cases
        if (n <= 10) return -1;

        // 1) walk backwardly, when the digit is ascending add to list, when meet smaller digit, it's swap point;
        List<Integer> list = new ArrayList<>();
        while (n > 0) {
            int curr = n % 10;
            n /= 10;
            if (list.size() == 0 || curr >= list.get(list.size() - 1)) {
                list.add(curr);
            } else { // found swap point, find greater digit
                int i = list.size() - 1;
                while (i >= 1 && curr < list.get(i-1)) i--;
                int tmp = list.get(i);
                list.set(i, curr);
                n = n * 10 + tmp;
                break;
            }
        }

        if (n == 0) return -1; // all digits ascending, no swap

        long res = n;
        for (int d : list) {
            res = res * 10 + d;
        }

        if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) return -1;
        else return (int) res;
    }
}

/*
1) walk backwardly, when the digit is ascending add to list, when meet smaller digit, it's swap point; 2) iterate the list to find the smallest digit greater than current one, swap then; 3) get the rest from list, it's in ascending order.
*/