LeetCode 670 最大交换[暴力 贪心] HERODING的LeetCode之路

解题思路：
由于给定的位数最大为8位，那么即使用暴力的方式最多也只要交换28次，所以第一种方法就是暴力交换任意两位，找到找到最大值并返回，代码如下：

class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        int n = s.size();
        int maxNum = num;
        for(int i = 0; i < n; i ++) {
            for(int j = i + 1; j < n; j ++) {
                // 换过来
                swap(s[i], s[j]);
                maxNum = max(maxNum, stoi(s));
                // 换回去
                swap(s[i], s[j]);
            }
        }
        return maxNum;
    }
};

时间复杂度： O(log² num)
空间复杂度： O(log num)

第二种方法是通过贪心的方式，定义一个最大下标，指向每位最大的数，再定义两个下标，指向想要交换的位数，从后往前遍历整数，遇到大的更新最大下标，遇到小的更新交换的下标，代码如下：

class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        int n = s.size();
        int maxIdx = n - 1;
        int idx1 = -1, idx2 = -1;
        for(int i = n - 1; i >= 0; i --) {
            if(s[i] > s[maxIdx]) {
                maxIdx = i;
            } else if(s[i] < s[maxIdx]) {
                idx1 = i;
                idx2 = maxIdx;
            }
        }
        if(idx1 >= 0) {
            swap(s[idx1], s[idx2]);
            return stoi(s);
        } 
        return num;
    }
};

时间复杂度： O(log num)
空间复杂度： O(log num)