670. Maximum Swap

// in the number, every digit has its own weight, like a digit needs to multiply 1000, while another
// needs to multiply 10, so we need try our best to let a big digit to the position has most weight
// at the same time, to decrease the loss of the exchange(we let a small digit to replace a big
// digit), we need the most right proper digit, which has the least weight, to exchange so we find
// every digit's most right index, then we use a most right big digit to replace a most left small
// digit
class Solution {
public:
    int maximumSwap(int num) {
        vector<int> digitLastIndex(10);
        string numString(to_string(num));
        for (int i = 0; i < numString.size(); ++i) {
            digitLastIndex[numString[i] - '0'] = i;
        }

        for (int i = 0; i < numString.size(); ++i) {
            for (int digit = 9; digit > numString[i] - '0'; --digit) {
                if (digitLastIndex[digit] > i) {
                    swap(numString[i], numString[digitLastIndex[digit]]);

                    // we could only exchange once, so if we swap, we return
                    return stoi(numString);
                }
            }
        }

        // if the origin number is the best one, we will not swap any digits and return, so we just
        // return the origin number
        return num;
    }
};