Description

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:

1. The given number is in the range [0, 10⁸]

Solution

Greedy

通過找規(guī)律可以發(fā)現(xiàn)碰声，從前往后遍歷digit膝蜈，如果發(fā)現(xiàn)digit i 后面有比它大的元素宣渗，則 i 就是要被交換的位置债蜜，j 是 i 往后最大的元素的下標(biāo)（如果最大元素相等則找到最后一個下標(biāo)），交換 i 和 j 即可蛛碌。

class Solution {
    public int maximumSwap(int num) {
        char[] arr = String.valueOf(num).toCharArray();
        int n = arr.length;
        int[] maxIdx = new int[n];
        maxIdx[n - 1] = n - 1;
        
        for (int i = n - 2; i >= 0; --i) {
            if (arr[i] <= arr[maxIdx[i + 1]]) {
                maxIdx[i] = maxIdx[i + 1];
            } else {
                maxIdx[i] = i;
            }
        }
        
        for (int i = 0; i < n - 1; ++i) {
            if (arr[i] < arr[maxIdx[i]]) {
                swap(arr, i, maxIdx[i]);
                break;
            }
        }
        
        return Integer.parseInt(String.valueOf(arr));
    }
    
    public void swap(char[] arr, int i, int j) {
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

上面的寫法不免繁瑣聂喇，可以用枚舉法來簡化。因為十進制數(shù)字每一位都在[0, 9]之間，可以用一個大小為10的int[] last保存每個值對應(yīng)的最大idx希太。

class Solution {
    public int maximumSwap(int num) {
        char[] arr = String.valueOf(num).toCharArray();
        int n = arr.length;
        int[] last = new int[10];
        for (int i = 0; i < n; ++i) {
            last[arr[i] - '0'] = i;
        }
        
        for (int i = 0; i < n; ++i) {
            for (int d = 9; d > arr[i] - '0'; --d) {
                if (last[d] > i) {
                    swap(arr, i, last[d]);
                    // break won't work because of embedded loop, return directly
                    return Integer.parseInt(String.valueOf(arr));
                }
            }
        }
        
        return num;
    }
    
    public void swap(char[] arr, int i, int j) {
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}