Java solution, O(n) time

• if the current letter is larger than the previous letter, it means there always exists a swap that can obtain a larger number. So find this letter, and iterate the letters after it to get a max letter, then swap to get a bigger number. For example, if the num is 763425, 7 >= 6 >= 3, 3 < 4, it means that a number after 3 can be moved to the front to get a larger number. It can be found that the biggest letter after 3 is 5. then iterate from 7, 6, 3 to find the first number smaller than 5, which is 3, so the result is 765423.

``````public int maximumSwap(int num) {
char[] s = (num + "").toCharArray();
char pre = '9';
int i = 0;
for (; i < s.length; i++) {
if (s[i] > pre) break;
pre = s[i];
}
int maxIndex = i;
if (maxIndex == s.length) return num;
for (int j = i; j < s.length; j++) {
if (s[j] >= s[maxIndex]) {
maxIndex = j;
}
}
for (int k = 0; k < i; k++) {
if (s[k] < s[maxIndex]) {
char p = s[k];
s[k] = s[maxIndex];
s[maxIndex] = p;
return Integer.parseInt(new String(s));
}
}
return num;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.