670. Maximum Swap.java

题目：非负正数，交换其中两位一次，使其变成最大的数
Input: 2736
Output: 7236
  
Input: 9973
Output: 9973

    k:  0,1,2,3,4,5,6,7,8,9
digits:[2,7,5,6]
buckets:    0     2 3 1
从buckets后面往前找，k=7时，原数组下标是1，在2对应的0之后，所以直接7和2换，返回。
如果是9837这个数，i=0时(9)找不到，i=1时(8)找不到，i=2时(3)找到其后比他最大的是7，所以交换3和7.

class Solution {
    public int maximumSwap(int num) {
        char[] digits = Integer.toString(num).toCharArray(); // 这个转换好：int-String-charArray
        
        int[] buckets = new int[10];  //相当于把原数组的key-value倒过来了。存的是每个数在原来数组的下标
        for (int i = 0; i < digits.length; i++) {
            buckets[digits[i] - '0'] = i;
        }
        
        for (int i = 0; i < digits.length; i++) {
            for (int k = 9; k > digits[i] - '0'; k--) { //从后往前找，保证下标是递减的，就是先找最大的，看他的值（原数组下标）比i大（原数组在其                                                           后）就换过来
                if (buckets[k] > i) {
                    char tmp = digits[i];
                    digits[i] = digits[buckets[k]];
                    digits[buckets[k]] = tmp;
                    return Integer.valueOf(new String(digits));   //找到就交换，return  （因为倒着找的，第一个找到的就是排在其后最大的数）
                }
            }
        }
        
        return num;
    }
}