Java solution, O(n) time


  • 0
    X

    if the current letter is larger than the previous letter, it means there always exists a swap that can obtain a larger number. So find this letter, and iterate the letters after it to get a max letter, then swap to get a bigger number. For example, if the num is 763425, 7 >= 6 >= 3, 3 < 4, it means that a number after 3 can be moved to the front to get a larger number. It can be found that the biggest letter after 3 is 5. then iterate from 7, 6, 3 to find the first number smaller than 5, which is 3, so the result is 765423.

    public int maximumSwap(int num) {
            char[] s = (num + "").toCharArray();
            char pre = '9';
            int i = 0;
            for (; i < s.length; i++) {
                if (s[i] > pre) break;
                pre = s[i];
            }
            int maxIndex = i;
            if (maxIndex == s.length) return num;
            for (int j = i; j < s.length; j++) {
                if (s[j] >= s[maxIndex]) {
                    maxIndex = j;
                }
            }
            for (int k = 0; k < i; k++) {
                if (s[k] < s[maxIndex]) {
                    char p = s[k];
                    s[k] = s[maxIndex];
                    s[maxIndex] = p;
                    return Integer.parseInt(new String(s));
                }
            }
            return num;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.