友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
670. 最大交换
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736 输出: 7236 解释: 交换数字2和数字7。
示例 2 :
输入: 9973 输出: 9973 解释: 不需要交换。
注意:
-
给定数字的范围是
[0, 108]
思路分析
如何进行“最大交换”？其实很简单：从后面的数字中，找出一个最大数与最高位进行交换。如果后面的最大数小于等于最高位的数字，则把最高位“向后”移一位，再从剩下的数字中寻找最大的数字。
有一点需要特别注意，如果后面的数字的最大数存在多个，则最高位需要跟最低位的数字进行交换。（保持高位的最大数字不变，可以保证数字更大。）
网友对贪心算法的一句话总结：每一位数字应该不小于所有排它后面的数字，否则找最大的且排最后面的数字与之交换。
-
一刷
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
61
62
63
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-28 23:00:28
*/
public int maximumSwap(int num) {
List<Integer> digits = getDigits(num);
if (digits.size() < 2) {
return num;
}
// 不标注是否交换，只击败了 31%，加后，击败 100%
boolean swapped = false;
for (int i = digits.size() - 1; i > 0; i--) {
int idx = getMaxNumIndex(digits, i - 1);
if (digits.get(idx) > digits.get(i)) {
int tmp = digits.get(i);
digits.set(i, digits.get(idx));
digits.set(idx, tmp);
swapped = true;
break;
}
}
if (swapped) {
return digitToNum(digits);
} else {
return num;
}
}
private int digitToNum(List<Integer> digits) {
int result = digits.getLast();
for (int i = digits.size() - 2; i >= 0; i--) {
result *= 10;
result += digits.get(i);
}
return result;
}
private int getMaxNumIndex(List<Integer> digits, int index) {
int max = Integer.MIN_VALUE;
int result = -1;
for (int i = 0; i <= index; i++) {
if (max < digits.get(i)) {
max = digits.get(i);
result = i;
}
}
return result;
}
private List<Integer> getDigits(int num) {
List<Integer> result = new ArrayList<>();
if (num == 0) {
result.add(0);
return result;
}
while (num > 0) {
int digit = num % 10;
result.add(digit);
num /= 10;
}
return result;
}