670 Maximum Swap

Maximum Swap

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: 9973
Output: 9973
Explanation: No swap.

Note:

1. The given number is in the range [0, 108]

-------------------------------------
Solution #1, 所有上升的数字都有可能被换到前面，拐点之前下降的则不会。找拐点之后最大的往前换，如果有相同的则取index靠后的。
9872345, 2为拐点，987不可能往前换，345则可能往前换
654123439，1为拐点，23439中最大的9可以往前换

class Solution {
    public int maximumSwap(int num) {
        char[] A = Integer.toString(num).toCharArray();
        
        int i = 1;
        for (; i < A.length; i++) {
            if (A[i] > A[i - 1]) break;
        }
        
        int max = -1;
        for (; i < A.length; i++) {
            if (max == -1 || A[max] - '0' <= A[i] - '0') {
                max = i;
            }
        }
        
        if (max == -1) return num;
        
        for (int j = 0; j < A.length; j++) {
            if (A[j] < A[max]) {
                char temp = A[j];
                A[j] = A[max];
                A[max] = temp;
                return Integer.valueOf(new String(A));
            }
        }
        
        return num;
    }
}

Solution #2, 把0-9每个数的位置预先存上，再从左遍历原数字，如果发现它右方有数字比它大，则进行交换，返回结果

class Solution {
    public int maximumSwap(int num) {
        char[] A = Integer.toString(num).toCharArray();
        int[] pos = new int[10];
        
        for (int i = 0; i < A.length; i++) {
            char c = A[i];
            pos[c - '0']  = i;
        }
        
        for (int i = 0; i < A.length; i++) {
            int val = A[i] - '0';
            for (int j = 9; j > 0; j--) {
                if (val >= j) break;
                if (pos[j] > i) {
                    char temp = A[pos[j]];
                    A[pos[j]] = A[i];
                    A[i] = temp;
                    return Integer.valueOf(new String(A));
                }
            }
        }
        
        return num;
    }
}