题目描述

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

样例

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

输入: 9973
输出: 9973
解释: 不需要交换。

算法

(贪心) $O(\log n)$

1. 首先找到整个数字中，从最高位到最低位出现严格递增的第一个位置 t，即 s[t - 1] < s[t]。若不存在这样的 t，则不需要交换。
2. 在 t 到最低位中找到最大的数字所在的位置 maxi，如果有多个，取最小的位。我们取出这个的这个 maxi是希望能与 t 前边的一位数位进行交换，期望获得更大的数字；而出现多个最大数字的情况下，需要保证交换后的数字尽可能大，所以取低位上的大数字会更优。
3. 从高位开始，如果出现 s[i] < s[maxi]，则交换位置即可。

时间复杂度

• 每个数位遍历常数次，故时间复杂度为 $O(\log n)$。

C++ 代码

class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        int l = s.length(), t = -1;
        for (int i = 0; i < l - 1; i++)
            if (s[i] < s[i + 1]) {
                t = i + 1;
                break;
            }
        if (t == -1)
            return num;
        int maxi = t;
        for (int i = t + 1; i < l; i++)
            if (s[maxi] <= s[i])
                maxi = i;
        for (int i = 0; i < l; i++)
            if (s[i] < s[maxi]) {
                swap(s[i], s[maxi]);
                break;
            }
        int ans = 0;
        for (int i = 0; i < l; i++)
            ans = ans * 10 + s[i] - '0';
        return ans;
    }
};