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
| class Solution {
public int maximumSwap(int num) {
char[] numArray = String.valueOf(num).toCharArray();
int[] greatestRight = new int[numArray.length];
int max = -1, maxIdx = -1;
for (int i = numArray.length - 1; i >= 0; i--) {
if (numArray[i] - '0' > max) {
max = numArray[i] - '0';
maxIdx = i;
greatestRight[i] = i;
} else {
greatestRight[i] = maxIdx;
}
}
for (int i = 0; i < numArray.length; i++) {
if (numArray[i] - '0' < numArray[greatestRight[i]] - '0') {
swap(numArray, i, greatestRight[i]);
return Integer.parseInt(new String(numArray));
}
}
return num;
}
private void swap(char[] numArray, int i, int j) {
char temp = numArray[i];
numArray[i] = numArray[j];
numArray[j] = temp;
}
}
|
先看第0位, 我们想知道它的右边比它大的值中最大的是谁, 如果有多个最大, 我们想要最右边的那个. 这样的话我们就可以倒着遍历. 然后记录遍历过程中遇到的最大值以及它的index. 如果在某个位置发现此时自己的值比max要小, 那么我们就知道当前位置右侧的比它大的值的index就是maxIdx. 如果遇到的值和记录的值一样大, 我们不需要更新max以及maxIdx, 因为我们想要的是右侧比我们大的值, 其中最大是越远越好. 因此第7行不能是大于等于而只能是等于. 一旦更新, 那么如果下一个值比这个max小, 比它大的值的index就会取离它近的那个而不是远的那个.
时间复杂度: O(n) n是num的长度.
空间复杂度: O(n) 因为用到了numArray和greatestRight.
当然n不超过9, 时间复杂度和空间复杂度都可以认为是O(1).
