算法题：最大交换

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字 2 和数字 7。
示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。
注意:

给定数字的范围是 [0, 108]

代码：
我们首先会想到，如果我们在第一位的后面能够找到比第一位大的数，那么是不是可以直接将他两交换，如果没找到的话我们是不是希望在第二位后面找到比第二位大的数来交换。简单方法是直接遍历。但复杂度高。如果我们可以先一次遍历找到数 0-9 出现的最后位置。可以使用一个简单 hash 方法。

class Solution {
    public int maximumSwap(int num) {
        char[] A = Integer.toString(num).toCharArray();
        int[] last = new int[10];
        for (int i = 0; i < A.length; i++) {
            last[A[i] - '0'] = i;
        }

        for (int i = 0; i < A.length; i++) {
            for (int d = 9; d > A[i] - '0'; d--) {
                if (last[d] > i) {
                    char tmp = A[i];
                    A[i] = A[last[d]];
                    A[last[d]] = tmp;
                    return Integer.valueOf(new String(A));
                }
            }
        }
        return num;
    }
}