LeetCode_贪心算法_中等_670.最大交换

1.题目

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

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

示例 2：
输入: 9973
输出: 9973
解释: 不需要交换。

注意：
给定数字的范围是 [0, 10⁸]

2.思路

（1）贪心算法
该题可用贪心算法来解决，具体步骤如下：
① 为了方便遍历 num 每一位上的数字，我们使用长度为 9 的数组 digits 来保存 num 上的每一位（因为给定数字的范围是 [0, 10⁸]，所以数组 digits 的长度为 9 就可以了，并且存储的方式是 digits[8] 存储 num 的个位、digits[7] 存储 num 的十位…，以此类推）。

② 将 num 每一位上的数字存储到数组 digits 中，同时计算出 num 所有位上的数字的最大值 maxDigit。

③ 从数组 digits 中第一个不为 0 的元素开始遍历：
1）如果当前位上的数字就是最大值，那么该位肯定不需要交换，进行下一次遍历；
2）如果当前位上的数字小于最大值，则有可能需要交换，

• 先求出 restMax 和 restMaxIndex，它们分别表示 digits[i…length - 1] 中的最大值以及对应的下标；
• 如果当前位上的数字小于 restMax，故将 digits[i] 与 digits[restMaxIndex] 进行交换，然后直接退出遍历即可；

④ 数组 digits 中的数字组成的数即为最终的答案；

3.代码实现（Java）

//思路1————贪心算法
class Solution {
    public int maximumSwap(int num) {
        if (num < 10) {
            return num;
        }
        int[] digits = new int[9];
        int length = digits.length;
        int index = length - 1;
        // maxDigit 为 num 所有位上的数字的最大值
        int maxDigit = 0;
        while (num != 0) {
            int curDigit = num % 10;
            digits[index--] = curDigit;
            maxDigit = Math.max(maxDigit, curDigit);
            num /= 10;
        }
        // digits[0...index] 中的元素全为 0，故从 digits[index + 1] 开始遍历
        for (int i = index + 1; i < length; i++) {
            /*
                (1) 如果当前位上的数字就是最大值，那么该位肯定不需要交换
                (2) 如果当前位上的数字小于最大值，则有可能需要交换
            */
            if (digits[i] < maxDigit) {
                // restMax 和 restMaxIndex 分别表示 digits[i...length - 1] 中的最大值以及对应的下标
                int restMax = digits[i];
                int restMaxIndex = i;
                for (int j = i + 1; j < length; j++) {
                	/*
						(1) 注意这里必须是 restMax <= digits[j]，否则可能会出错
						(2) 例如，num = 1993，如果写成 restMax < digits[j]，虽然 restMax = 9，但是 restMaxIndex = 2，
							交换 digits[3] = 1 与 digits[2] = 9 后，得到 num = 9193，显然这并非正确答案，
							正确答案应由 digits[3] = 1 与 digits[1] = 9 交换得到，即为 9913。
						(3) 所以写成 restMax <= digits[j] 是为了尽可能让处于低位的较大的数字被交换到高位
					*/
                    if (restMax <= digits[j]) {
                        restMax = digits[j];
                        restMaxIndex = j;
                    }
                }
                if (digits[i] < restMax) {
                    // 当前位上的数字小于 restMax，故需要将 digits[i] 与 digits[restMaxIndex] 进行交换
                    int tmp = digits[i];
                    digits[i] = restMax;
                    digits[restMaxIndex] = tmp;
                    //交换结束后直接退出遍历
                    break;
                }
            }
        }
        //将 digits[index + 1...length - 1] 中的数字组成的数即为最终的答案
        int res = 0;
        int x = 1;
        for (int i = length - 1; i > index; i--) {
            res += digits[i] * x;
            x *= 10;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60