0670. Maximum Swap #

class Solution {
    public int[] seperateDigits(int num) {
        Stack<Integer> stack = new Stack<>();
        while (num > 0) {
            stack.push(num % 10);
            num /= 10;
        }
        int[] ret = new int[stack.size()];
        for (int i = 0; i < ret.length; i++) ret[i] = stack.pop();
        return ret;
    }

    public int[] findRightMaximum(int[] digits) {
        int N = digits.length;
        int[] maximum = new int[N];
        for (int i = N-1; i >= 0; i--) {
            maximum[i] = i == N - 1 ? digits[i] : Math.max(digits[i], maximum[i+1]);
        }
        return maximum;
    }

    public void swap(int[] digits, int i, int j) {
        int temp = digits[i];
        digits[i] = digits[j];
        digits[j] = temp;
    }

    public int maximumSwap(int num) {
        if (num == 0) return 0;

        int[] digits = seperateDigits(num);
        int[] rightMaximum = findRightMaximum(digits);

        for (int i = 0; i < digits.length; i++) {
            if (rightMaximum[i] != digits[i]) {
                int pos = -1;
                for (int j = digits.length-1; j>i; j--) {
                    if (digits[j] > digits[i] && (pos == -1 || digits[j] > digits[pos])) pos = j;
                }
                swap(digits, i, pos);
                break;
            }
        }

        int ans = 0;
        for (int i = 0; i < digits.length; i++) {
            ans += digits[i] * Math.pow(10, digits.length-1-i);
        }
        return ans;
    }
}