Java O(n) Stack Solution


  • 0
    public int maximumSwap(int num) {
        if (num == 0) return 0;
        String s = "" + num;
        char[] strs = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        int smaller = Integer.MAX_VALUE; // Index of the smaller digit
        int bigger = Integer.MAX_VALUE; // Index of the bigger digit
        for (int i = 0; i < strs.length; i++) {
            if (stack.isEmpty()) {
                if (smaller == Integer.MAX_VALUE) {
                    stack.push(i);
                }
                else {
                    if (strs[i] >= strs[bigger] ){
                        bigger = i;
                    }
                }
            }
            else {
                int top = stack.peek();
                if (smaller == Integer.MAX_VALUE && strs[i] < strs[top]) {
                    stack.push(i);
                }
                else {
                    while (!stack.isEmpty() && strs[i] > strs[stack.peek()]) {
                        int current = stack.pop();
                        if (current < smaller ) {
                            smaller = current;
                        }
                    }
                    if (bigger == Integer.MAX_VALUE || strs[bigger] <= strs[i] || bigger <= smaller) { 
                        // if bigger digit not found or current digit is bigger or the bigger index is already smaller than the smaller index like "99901".
                        bigger = i;
                    }
                }
            }
        }
        if (smaller != Integer.MAX_VALUE && bigger != Integer.MAX_VALUE) {
            char temp = strs[smaller];
            strs[smaller] = strs[bigger];
            strs[bigger] = temp;
        }
        int res = 0;
        for (int i = 0; i < strs.length; i++) {
            res = res * 10 + (int)(strs[i] - '0');
        }
        return res;
    }

Log in to reply
 

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