# Java, PriorityQueue with detail explanation, O(NlogN)

1. char[] chars = (""+num).toCharArray();

2. PriorityQueue pq store the index of the digit in num, large digit first; for same digit, lower index first

3. Iterate the chars, find the first mismatch, chars[i] != chars[pq.poll()]; at this time, max = chars[pq.poll()] is the largest digit we can put here.

4. Then we want to swap chars[i] with the last appearance of the digit max (e.g. 98368, swap 3 with the last 8);

Example:
input: 9-8-3-6-8
index: 0-1-2-3-4

pq : 0-1-4-3-2

for (int i = 0; i < chars.length; i++)
chars[0] == chars[pq.poll() = 0]; i++
chars[1] == chars[pq.poll() = 1]; i++
chars[2] != chars[pq.poll() = 4]; i++

so we want to swap chars[2] with chars[4]

``````class Solution {
public int maximumSwap(int num) {
char[] chars = (""+num).toCharArray();
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
@Override
public int compare(Integer a, Integer b) {
if (chars[a] == chars[b]){
return a-b; //idx increasing
}
return chars[b] - chars[a]; // digit desending
}
});
for (int i = 0; i < chars.length; i++)
pq.offer(i);

for (int i = 0; i < chars.length; i++){
int idx = pq.poll();
char max = chars[idx];
if (chars[i] != max) {
char ch = chars[i];
while (!pq.isEmpty() && chars[pq.peek()] == max)
idx = pq.poll();
chars[i] = max;
chars[idx] = ch;
break;
}
}

return Integer.parseInt(new String(chars));
}
}
``````

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