2022-09-13力扣每日一题（670. 最大交换）贪心

题目

670. 最大交换

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

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

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

思路：（三种思路）

1.暴力：遍历每个数字，每个数字都和自己后面的所有数字比较，有比较大的就交换位置，交换后就直接返回结果。（平均情况下时间复杂度较高）
2.全排列：题目中给的数字是整数，由于对于整数num 的十进制数字位长最长为 8 位，任意两个数字交换一次最多有 28 种不同的交换方法，因此我们可以尝试遍历所有可能的数字交换方法即可，并找到交换后的最大数字即可。（来源：力扣官方；这个思路虽然不是最优解，但是不容易想到）
3.贪心：将当前位和后面最大的数字交换位置。我们可以反过来做，从右往左记录最大值，然后再和原数字找第一个不同的地方。
3.1预处理：将数字从后往前遍历，将遍历到的数字换成当前情况下最大的。
276534 ==》 776544
3.2交换最大的数字：将原数组和预处理后的数组比较，找到第一个不同的数字，将他们在数组中的位置交换（注意：交换的时候，要从数组最后面往前面找，避免数字出现重复的情况）

java代码实现

 class Solution {
        public int maximumSwap(int num) {
            //1.将数字转化为数组类型
            int[] copy1 = new int[String.valueOf(num).length()];
            int[] copy2 = new int[String.valueOf(num).length()];
            for (int i = copy1.length - 1; i >= 0; i--) {
                copy1[i] = num % 10;
                copy2[i] = num % 10;
                num /= 10;
            }

            //2.倒序遍历，从后往前，遇到最大值就记录，将小的地方全部换为最大值
            int max = Integer.MIN_VALUE;
            for (int i = copy1.length - 1; i >= 0; i--) {
                if (copy1[i] > max){
                    max = copy1[i];
                }else {
                    copy1[i] = max;
                }

            }

            //3.正序遍历，得到第一个被交换的位置，就可以知道哪个位置需要交换了
            for (int i = 0; i < copy2.length; i++) {
                if (copy1[i] != copy2[i]) {
                    //4.从后往前， 将后面的大数换成小数
                    for (int j =copy2.length - 1 ; j > i ; j--) {
                        if (copy2[j] == copy1[i]){
                            copy2[j] = copy2[i];
                            break;
                        }
                    }
                    //5.将当前位置换成最大值
                    copy2[i] = copy1[i];
                    break;

                }
            }

            //7.
            int ans = 0;
            for (int i = 0; i < copy2.length; i++) {
                ans = ans*10 + copy2[i];
            }
            return ans;


        }
    }