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


  • 9
    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.


Log in to reply
 

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