Leetcode 670. Maximum Swap

第一感就是从最左边数位开始查找，如果该数位的右边有更大的数，那么我们应该交换；进而想到应该维护一个数组，表示该数位右边的最大数字，这个数组可以通过由右向坐遍历一遍得到；再进一步想到，如果有多个相同的最大值，那么应该记录最靠右的那个index，这样交换之后的数更大。最后如果该数位本身已经是最大值了就不用交换。

时间复杂度： O(N)

空间复杂度: O(N) ，因为额外数组

class Solution {

public:

    int maximumSwap(int num) {

        string numStr = to_string(num);

        vector<int> rightLargest(numStr.size());

        int curMaxIndex = numStr.size()-1;

        for(int i=numStr.size()-1; i>=0; i--){

            if(numStr[i]-'0'>numStr[curMaxIndex]-'0'){

                rightLargest[i] = i;

                curMaxIndex = i;

            }else{

                rightLargest[i] = curMaxIndex;

            }

        }

        string res = numStr;

        for(int i=0; i<numStr.size(); i++){

            //this is critical, only swap if number in right max index is larger than current number

            if(numStr[rightLargest[i]]-'0' > numStr[i]-'0'){

                res[i] = numStr[rightLargest[i]];

                res[rightLargest[i]] = numStr[i];

                return stoi(res);

            }

        }

        return num;

    }

};