# Java solution by using Deque, o(n)space, o(n)time

• The basic idea is find the first number which is not on it's original position,
2527
5 is larger than 2, pop 2, add 5 to deque,
2 is less than 5, push to deque,
7 is larger than all number in deque, pop all, save it in deque
start from i = 0, and the head of deque, if the index in deque equal to the i, meaning the number is on its original position, deque remove first, check the next, the first one which has different number with i is the number we want to swap with i. In this example 7's index is 3, is different from 0, so we want to swap 7 with 2. Search the array to find first number equal to 7 from right to left to swap with 2

``````class Solution {
public int maximumSwap(int num) {
char[] number = (num + "").toCharArray();
for (int i = 0; i < number.length; i++) {
if (deque.isEmpty() || number[i] - '0' <= number[deque.getLast()] - '0') {
} else {
while (!deque.isEmpty() && number[i] - '0' > number[deque.getLast()] - '0') {
deque.removeLast();
}
}
}
if (deque.size() != number.length) {
int j = 0;
while (deque.getFirst() == j) {
deque.removeFirst();
j++;
}
char target = number[deque.getFirst()];

for (int k = number.length - 1; k >= 0; k--) {
if (target == number[k]) {
char temp = number[j];
number[j] = target;
number[k] = temp;
break;
}
}
}
return Integer.valueOf(new String(number));
}
}

``````

• Make it a little bit more concise.

``````class Solution {
public int maximumSwap(int num) {
Deque<Integer> stack = new ArrayDeque<>();
char[] charArr = String.valueOf(num).toCharArray();
for (int i = 0; i < charArr.length; i++) {
while (!stack.isEmpty() && charArr[stack.peek()] <= charArr[i]) {
stack.pop();
}
stack.push(i);
}

for (int i = 0; i < charArr.length; i++) {
int idx = stack.peekLast();
if (idx != i) {
if (charArr[idx] == charArr[i]) {
continue;
}
char temp = charArr[idx];
charArr[idx] = charArr[i];
charArr[i] = temp;
break;
}
stack.pollLast();
}
return Integer.parseInt(String.valueOf(charArr));
}
}
``````

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