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

1.题目

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

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

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

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

2.思路

（1）贪心算法 该题可用贪心算法来解决，具体步骤如下： ① 为了方便遍历 num 每一位上的数字，我们使用长度为 9 的数组 digits 来保存 num 上的每一位（因为给定数字的范围是 [0, 108]，所以数组 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