原题链接在这里：https://leetcode.com/problems/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:
- The given number is in the range [0, 108]
题解：
想要组成最大的数字，就是要把尽量开头的digit换成后面比他大的最大digit. 若这个最大digit有重复, 去最右侧的那个.
It is about how to get the index of largest digit after current one.
所以先把么个digit出现的last index记录下来.
Iterating num, check from max = 9 to check if max last occurance index is after i. If yes, swap.
Time Complexity: O(n). n是原有num digits的位数.
Space: O(n).
AC Java:
class Solution {
public int maximumSwap(int num) {
char [] digits = Integer.toString(num).toCharArray();
int [] lastInd = new int[10];
for(int i = 0; i<digits.length; i++){
lastInd[digits[i]-'0'] = i;
}
for(int i = 0; i<digits.length; i++){
for(int k = 9; k>digits[i]-'0'; k--){
if(lastInd[k] > i){
char temp = digits[i];
digits[i] = digits[lastInd[k]];
digits[lastInd[k]] = temp;
return Integer.valueOf(new String(digits));
}
}
}
return num;
}
}