Maximum Swap

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:

1. 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));
    }
}