Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.
Example 1:
Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.
Example 2:
Input: 9973
Output: 9973
Explanation: No swap.
Note:
The given number is in the range [0, 10^8]
class Solution {
public int maximumSwap(int num) {
char[] str = Integer.toString(num).toCharArray();
Deque<Integer> stack = new LinkedList<>();
int toSwap = -1, fromSwap = -1;
for (int i = 0; i < str.length; i++) {
char c = str[i];
int bestCurrentSwap = -1;
while (stack.size() != 0 && str[stack.peek()] < c)
// We want to swap with MSDigit, for max result
bestCurrentSwap = stack.pop();
// If we have not found any pair to swap until now
if (toSwap == -1 && fromSwap == -1) {
toSwap = bestCurrentSwap;
fromSwap = bestCurrentSwap == -1 ? -1 : i;
}
// Else if we have found a pair before, then we need to make sure
// that our current digit > previous 'fromSwap' digit
// Otherwise 'fromSwap' digit is already giving us the best result
else if (c >= str[fromSwap]) {
fromSwap = i;
// We want to swap with MSDigit, for max result
toSwap = Math.min(toSwap, bestCurrentSwap == -1 ? Integer.MAX_VALUE : bestCurrentSwap);
}
stack.push(i);
}
if (toSwap == -1 && fromSwap == -1)
return num;
char t = str[toSwap];
str[toSwap] = str[fromSwap];
str[fromSwap] = t;
return Integer.parseInt(String.valueOf(str));
}
}