670 Maximum Swap¶

Problem¶

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]

Solutions¶

class Solution {
    public int maximumSwap(int num) {
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            sb.insert(0, num % 10);
            num = num / 10;
        }
        char[] chars = sb.toString().toCharArray();
        char[] maxs = new char[chars.length];
        int[] indexes = new int[chars.length];
        for (int i = chars.length - 1; i >= 0; i --) {
            if (i == chars.length - 1) {
                maxs[i] = chars[i];
                indexes[i] = i;
            }
            else {
                if (chars[i] > maxs[i + 1]) {
                    maxs[i] = chars[i];
                    indexes[i] = i;
                }
                else {
                    maxs[i] = maxs[i + 1];
                    indexes[i] = indexes[i + 1];
                }
            }
        }
        for (int i = 0; i < chars.length; i ++) {
            if (maxs[i] > chars[i]) {
                //swap i and indexes[i];
                char c = chars[i];
                chars[i] = chars[indexes[i]];
                chars[indexes[i]] = c;
                break;
            }
        }
        int res = 0;
        for (int i = 0; i < chars.length; i ++) {
            res = res * 10 + (chars[i] - '0');
        }
        return res;
    }
}