algo-aha

最多交换一次数字、使数尽量大

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

int maximumSwap(int num) {
    // 从左往右看各位置，看有没有比当前数字尽量大的数字在最后面，有就交换
    string s = to_string(num);
    const int N = s.size();
    vector<int> lastIdx(10, -1);
    for (int i = 0; i < N; i++) {
        lastIdx[s[i] - '0'] = i;
    }
    
    for (int i = 0; i < N; i++) {
        for (int x = 9; x > s[i] - '0'; x--) {
            if (lastIdx[x] > i) {
                swap(s[i], s[lastIdx[x]]);
                return stoi(s);
            }
        }
    }
    return num;        
}