Leetcode Math 670 @Java－CONY的世界

670. 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]

這邊的思維是loop from MSB到LSB，然後每位要用往後找是否有比自己更大的

（不能用往前看，找比自己小的最大位，因為無法確定目前的數字換完就是最大的

ex. 98368 --> 98863，如果用往前找小的，會變成98638，但是其實最佳的換法是8跟3 換）

所以要用小的數往後找最大值來看（因為9一定會讓值是最大，不管在哪位）

一但找到就可以swap 後return

class Solution {
    public int maximumSwap(int num) {
        char[] nums = String.valueOf(num).toCharArray();
        int[] pos = new int[10];
        for(int index=0; index<nums.length; index++)
            pos[nums[index] - '0'] = index;
        for(int index=0; index<nums.length; index++) {
            for(int val=9; val > nums[index]-'0'; val--) {
                if(pos[val] > index) {
                    char tmp = nums[pos[val]]; 
                    nums[pos[val]] = nums[index];
                    nums[index] = tmp;
                    return Integer.valueOf(new String(nums));
                }
            }
        }
        return num;
    }
}