图解LeetCode——670. 最大交换（难度：中等）

一、题目

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

二、示例

2.1> 示例 1 :

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

2.2> 示例 2 :

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

注意:

给定数字的范围是 [0, 10^8]

三、解题思路

3.1> 思路1：排序 + 对比交换

根据题意描述，我们要交换两个数，使其交换后得到最大值。那么从高位开始，找到第一个没按照降序排列的数，就是我们需要替换的数了。所以，我们可以通过Arrays.sort(...)方法，将原有数组进行排序（默认是升序排序，当与原数组对比的时候，我们可以采用对排序后的数组执行倒序遍历即可）。

如下图所示：将原数组与排序数组进行对比，发现第3个位置是不对的，应该是8，但是原数组却是3，所以我们将原数组的3替换为8。

 那么，下一步，就是需要将原数组的8替换为3了。此时，为了保证交互后得到最大值，所以我们需要采用逆序遍历的方式，从数组的尾部开始找8，当找到后，将8替换为3即可。

3.2> 思路2：倒序遍历最大下标 + 对比交换

在思路2中，我们首先创建一个数组maxIndexs，它是用来存放数组下标index用的。那存放什么index呢？就是说，我们逆序遍历数组numArr，将当前遍历过的数组元素中，最大值的下标index存入到相应的maxIndexs中。如下图所示：

• 遍历numArr[8]，当前最大值就是它本身（下标index=8），所以maxIndexs[8]被赋值8；
• 遍历numArr[7]，当前最大值就是它本身（下标index=7），所以maxIndexs[7]被赋值7；
• 遍历numArr[6]，当前最大值就是它本身（下标index=6），所以maxIndexs[6]被赋值6；
•  ... ...

从上图中我们可以发现一个规律，就是在已经降序排序好的数组中，maxIndexs中存储的也就是numArr中该元素自身的下标，也就是说，每个元素在判断最大值的时候，都是与它右侧的所有元素进行对比的。那么，根据这个规律，我们再来尝试解答本题。

如下图所示，numArr逆序遍历后，maxIndexs=[0,4,4,4,4,5]，那么我们从头开始对比 numArr[i] 和 numArr[maxIndexs[i]] 的值，如果发现不同了，那么互换的下标就是 i 和 maxIndexs[i] 。

四、代码实现

4.1> 代码1：排序 + 对比

class Solution {
    public int maximumSwap(int num) {
        char[] num1 = String.valueOf(num).toCharArray();
        char[] num2 = String.valueOf(num).toCharArray();
        Arrays.sort(num2);
 
        Character lc = null, hc = null;
        for (int i = 0; i < num1.length; i++) {
            if (num1[i] != num2[num1.length - i - 1]) {
                lc = num1[i];
                hc = num2[num1.length - i - 1];
                num1[i] = num2[num1.length - i - 1];
                break;
            }
        }
 
        if (lc != null) {
            for (int i = num1.length - 1; i >= 0; i--) {
                if (hc.equals(num1[i])) {
                    num1[i] = lc;
                    break;
                }
            }
        }
 
        return Integer.valueOf(new String(num1));
    }
}

4.2> 代码2：倒序遍历最大下标 + 对比

class Solution {
    public int maximumSwap(int num) {
        char[] numArr = String.valueOf(num).toCharArray();        
        int[] maxIndexs = new int[numArr.length];
 
        int index = numArr.length - 1;
        for (int i = numArr.length - 1; i >= 0; i--) {
            if (numArr[i] > numArr[index]) index = i;
            maxIndexs[i] = index;
        }
 
        for (int i = 0; i < numArr.length; i++) {
            if (numArr[i] != numArr[maxIndexs[i]]) {
                char temp = numArr[i];
                numArr[i] = numArr[maxIndexs[i]];
                numArr[maxIndexs[i]] = temp;
                break;
            }
        }
 
        return Integer.valueOf(new String(numArr));
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」