670. Maximum Swap

https://leetcode.com/problems/maximum-swap/

整数内数字只让俩俩间swap最多一次，求能形成最大的数。要变大肯定是要把落在后面的大数和在前面的小数swap。观察例子98368可知对i （e.g. 3）找后面比它大的且是最大的数做替换。因为数字只可能是0~9，统计出每个数出现的最后位置然后遍历9~i做比较就能O(1)时间找到。

/*
 * @lc app=leetcode id=670 lang=cpp
 *
 * [670] Maximum Swap
 */

// @lc code=start
class Solution {
public:
    int maximumSwap(int num) {
        auto s = to_string(num);
        vector<int> last(10, -1);
        for (int i = 0; i < s.length(); ++i) {
            last[s[i] - '0'] = i;
        }
        for (int i = 0; i < s.length(); ++i) {
            for (int j = 9; j > (s[i] - '0'); --j) {
                if (last[j] <= i) continue;
                swap(s[i], s[last[j]]);
                return stoi(s);
            } 
        }
        return num;
    }
};
// @lc code=end