LeetCode：670. 最大交换（Java 贪心）

目录

670. 最大交换

题目描述：

实现代码与解析；

贪心

原理思路：

---

670. 最大交换

题目描述：

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

示例 1 :

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

示例 2 :

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

注意:

1. 给定数字的范围是 [0, 108]

实现代码与解析；

贪心

class Solution {public int maximumSwap(int num) {char[] chars = String.valueOf(num).toCharArray();int n = chars.length;char maxn = chars[n - 1];int maxIdx = n - 1;int r = -1; // 右边需要交换的位置int l = -1; // 左边需要交换的位置for (int i = n - 1; i >= 0; i--) {             if (chars[i] < maxn) { // 说明此位置可能为左交换位置l = i; // 更新左交换位置r = maxIdx; // 获取当前位置若为左交换位置时的右交换位置，也就是当前位置右侧的数中最大值位置}if (maxn < chars[i]) { // 从右向左已经遍历过的值中的最大值maxn = chars[i]; // 更新最大值maxIdx = i; // 更新最大值位置} }if (l >= 0) { // 大于等于0才交换，因为有可能数据不用动swap(chars, l, r);}StringBuilder res = new StringBuilder();for (int i = 0; i < n; i++) {res.append(chars[i]);}int res2 = Integer.parseInt(res.toString());return res2;}public void swap(char[] chars, int l, int r) {char t = chars[r];chars[r] = chars[l];chars[l] = t;}
}

原理思路：

        无论是什么解法，肯定思想是一样的。

        此题是核心就是从左到右，找到 第一个其右侧数中的最大值比当前数大的位置，进行交换。

        所以你可以进行两次for循环直接暴力，但是可以优化，就如我写的代码一样。

从右向左，逆向，边求最大值，边比较（找出交换位置）。

        具体细节，代码注释很详细了。需要注意一下可能不需要交换就是最大了，判断一下。