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


  • 0
    S

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

Log in to reply
 

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