问题：
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: 2736Output: 7236Explanation: Swap the number 2 and the number 7.
Example 2:
Input: 9973Output: 9973Explanation: No swap.
Note:
- The given number is in the range [0, 10^8]
解决：
① 暴力解决。
class Solution { //11ms
public int maximumSwap(int num) { String str = String.valueOf(num); char[] schar = str.toCharArray(); int res = num; int len = schar.length; for (int i = 0;i < len;i ++){ for (int j = i + 1;j < len;j ++){ swap(schar,i,j); res = Math.max(res,Integer.parseInt(String.valueOf(schar))); swap(schar,i,j); } } return res; } public void swap(char[] schar,int i,int j){ char tmp = schar[i]; schar[i] = schar[j]; schar[j] = tmp; } }②
我们希望置换后的数字最大，那么肯定希望将高位上的小数字和低位上的大数字进行置换，比如题目汇总的例子1。而如果高位上的都是大数字，像例子2那样，很有可能就不需要置换。
我们从高位向低位遍历，如果某一位上的数字小于其右边的最大数字，说明需要调换，由于最大数字可能不止出现一次，我们希望能跟较低位的数字置换，这样置换后的数字最大，所以我们就从低位向高位遍历来找那个最大的数字，找到后进行调换即可。
如对于1993这个数：
1 9 9 3
9 9 9 3 (dp数组，记录i之后的最大数)
9 9 1 3
建立好最大数组后，从头遍历原数字，发现1比9小，于是从末尾往前找9，找到后一置换，就得到了9913。
class Solution { //11ms
public int maximumSwap(int num) { if (num <= 10) return num; char[] schar = Integer.toString(num).toCharArray(); char[] dp = schar.clone();//记录i之后的最大值 for (int i = schar.length - 2;i >= 0;i --){ if (dp[i] < dp[i + 1]){ dp[i] = dp[i + 1]; } } for (int i = 0;i < schar.length;i ++){ if (schar[i] == dp[i]) continue; for (int j = schar.length - 1;j > i;j --){ if (schar[j] == dp[i]){ swap(schar,i,j); return Integer.parseInt(String.valueOf(schar)); } } } return Integer.parseInt(String.valueOf(schar)); } public void swap(char[] schar,int i,int j){ char tmp = schar[i]; schar[i] = schar[j]; schar[j] = tmp; } }③ 使用桶排序的思想，建了十个桶，分别代表数字0到9，每个桶存该数字出现的最后一个位置，也就是低位。这样我们从开头开始遍历数字上的每位上的数字，然后从大桶开始遍历，如果该大桶的数字对应的位置大于当前数字的位置，说明低位的数字要大于当前高位上的数字，那么直接交换这两个数字返回即可。
class Solution { //11ms
public int maximumSwap(int num) { char[] schar = String.valueOf(num).toCharArray(); int[] bucket = new int[10]; for (int i = 0;i < schar.length;i ++){ bucket[schar[i] - '0'] = i; } for (int i = 0;i < schar.length;i ++){ for (int k = 9;k > schar[i] - '0';k --){ if (bucket[k] <= i) continue; swap(schar,i,bucket[k]); return Integer.parseInt(String.valueOf(schar)); } } return num; } public void swap(char[] schar,int i,int j){ char tmp = schar[i]; schar[i] = schar[j]; schar[j] = tmp; } }④ 与上面相同的思路，但是只需要一个变量保存比当前值大的位置。
class Solution { //12ms
public int maximumSwap(int num) { char[] nums = String.valueOf(num).toCharArray(); for(int i = 0; i < nums.length; i++) { int indexJ = -1; for(int j = nums.length - 1; j > i; j--) { if(nums[j] > nums[i]) { if(indexJ == -1 || nums[j] > nums[indexJ]) indexJ = j; } } if(indexJ != -1) { swap(nums, i, indexJ); break; } } return Integer.parseInt(String.valueOf(nums)); } public void swap(char[] nums, int i, int j) { char temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }