The basic idea is find the first number which is not on it's original position,

2527

2 add to deque, here we push index instead of number

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();
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < number.length; i++) {
if (deque.isEmpty() || number[i] - '0' <= number[deque.getLast()] - '0') {
deque.addLast(i);
} else {
while (!deque.isEmpty() && number[i] - '0' > number[deque.getLast()] - '0') {
deque.removeLast();
}
deque.addLast(i);
}
}
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));
}
}
```