670. 最大交换（难度：中等）

题目链接：https://leetcode.cn/problems/maximum-swap/

题目描述：

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

示例 1 :

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

示例 2 :

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

注意:

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

解法：模拟+排序

根据题目描述，我们最多可以交换数字中的任意两位，让数字得到最大值。

那怎样的数字才算是最大的？

如果一个数字可以交换n位，那么我们得到的最大值，一定是将数字位重新由大到小排序得到的数字。

我们可以将数字的每一位拆解出来，然后由大到小进行排序。再去和原来的数字从最高位到最低位依次进行比较，找到的第一个不同的数字位（如原数字中当前位为a和最大数字当前位为b），就是我们要交换的位置，由于原数字中的当前位的下标一定是不变的，而最大数字当前位b，可能会有多个位的值都是b。

由于a 一定是小于 b 的，若想让交换后的数字尽可能的大，那么我们最好和最右边的b进行交换。

代码：

class Solution {
    public int maximumSwap(int num) {
        List<Integer> ds = new ArrayList<>();
        int t = num;

        String numStr = String.valueOf(num);

        while (t != 0) {
            ds.add(t % 10);
            t /= 10;
        }

        ds.sort((a,b) -> (b-a));

        for(int i = 0;i<ds.size();i++) {
            if(numStr.charAt(i) -'0' !=  ds.get(i)) {
                int index = numStr.lastIndexOf(String.valueOf(ds.get(i)));
                numStr = swap(numStr,i,index);
                break;
            }
        }
        return Integer.valueOf(numStr);
    }

    public String swap(String str, int i, int j) {
        char[] charArray = str.toCharArray();
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return new String(charArray);
    }
}