[C++] 3ms, O(n) time, O(n) space, DP solution


  • 13
    S

    We only need to record a position array (pos[i]) which represent the largest number index form the i position.

    For instance,
    input 9 8 6 3 8
    pos 0 4 4 4 4
    input[pos] 9 8 8 8 8

    Therefore, we only need to find the first input[i] != input[pos[i]]
    and swap it.

    Another example
    input 5 4 3 1 2
    pos 0 1 2 4 4
    input[pos] 5 4 3 2 2

    int maximumSwap(int num) {
        string numString = to_string(num);
        int n = numString.length();
        vector<int> dpPosition(n, -1);
            
        int curMaxPos = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            if (numString[i] > numString[curMaxPos]) {
                curMaxPos = i;
            }
            dpPosition[i] = curMaxPos;
        }
            
        for (int i = 0; i < n; i++) {
            if(numString[dpPosition[i]] != numString[i]) {
                swap(numString[i], numString[dpPosition[i]]);
                break;
            }
        }
            
        return stoi(numString);
    }
    

  • 0

    @suilan0602 brilliant idea.


  • 0
    A

    very clean and easy solution!!!! thank you
    we share the same idea, but your implementation is much better than me.


Log in to reply
 

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