670. Maximum Swap

桶排序 O(n) time O(10) space
思路就是从高位到低位扫描，对于每一位数字，找到其右侧比他大的所有数字里最大的那个数字，找到这个数字最后一次出现的位置，交换即可，因此需要统计每个数字最后一次出现的位置

class Solution {
public:
    int maximumSwap(int num) {
        int last[10] = {0};
        auto s = to_string(num);
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            last[s[i] - '0'] = i; // 记录所有数字最后出现的位置
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 9; j > s[i] - '0'; --j) {
                if (i < last[j]) { // 对于每个处于高位的数字，如果能找到一个比它大的在低位的数字，交换并返回
                    swap(s[i], s[last[j]]);
                    return stoi(s);
                }
            }
        }
        return num;
    }
};

桶排序 O(n) time O(n) space
0到9十个数字十个桶，扫描数字字符串，把每个数字出现的下标保存到对应数字的桶里
从9到0依次扫描桶，取出当前桶i最后一次出现的下标b[i].back()，然后扫描所有比当前桶对应的数字小的数字的桶j中的第一次出现的下标b[j].front()并找到最小的下标l，将其与桶i最后一次出现的下标b[i].back()，交换原字符串中的数字即可

class Solution {
public:
    int maximumSwap(int num) {
        vector<vector<int>> b(10);
        auto s = to_string(num);
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            b[s[i] - '0'].push_back(i);
        }
        for (int i = 9; i >= 0; --i) {
            if (b[i].empty()) continue;
            int l = b[i].back();
            for (int j = i - 1; j >= 0; --j) {
                if (b[j].empty()) continue;
                l = min(l, b[j].front());
            }
            if (l < b[i].back()) {
                swap(s[l], s[b[i].back()]);
                break;
            }
        }
        return stoi(s);
    }
};