LeetCode.670. 最大交换

题目

题目链接

分析

这道题的意思是我们只能交换一次，需要得到最大的数字。

我们的第一个想法就是要这个数字先变成一个数组，便于我们操作。
然后把数组最大的数放到第一个位置，如果最大的数字已经在第一个位置，那么就把次大的数放到第二个位置，依次递推…

如果数字为 nums =52767，我们肯定是要把最后一个7放到第一个位置，这样才能得到最大的数字，也即 72765。所以可以采取从后向前遍历的方式，只有大于的时候才更新下标即可。

总结：
我们先把这个数字变成一个数组，然后遍历这个数组，找到每一位后面最大的数字，如果这个最大的数字有多个，我们则取靠后位置的那个数字，一旦找到就结束遍历。

代码

class Solution {
    public int maximumSwap(int num) {
        if(num < 10) return num;
        char[] s = Integer.toString(num).toCharArray();
        for(int i = 0;i < s.length;i ++) {
            int maxIndex = i;
            // 如果遇到多个数字，取靠后面的数字，所以采取从后向前遍历的方式
            for(int j = s.length - 1;j >= i + 1;j --) {
                if(s[j] > s[maxIndex]) {
                    maxIndex = j;
                }
            }
            // 说明 i 后面有大于 s[i] 的数字
            if(maxIndex != i) {
                char temp = s[i];
                s[i] = s[maxIndex];
                s[maxIndex] = temp;
                return Integer.parseInt(new String(s));
            }
        }
        return num;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23