670. Maximum Swap 换个角度看问题

https://leetcode.com/problems/maximum-swap/description/

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

Example 1:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: num = 9973
Output: 9973
Explanation: No swap.

这乍一看极度简单题居然对我造成了不小的挑战。

先是在面试前刷过一次，当时大概是看这题评价很低，糊弄过去了，而且brutal force居然一次过，也就没放在欣赏。

直到面试时真正遇到这题才发现要想出非brutal force的解法并非那么简单。

Failure Attempt

面试当时给出了Priority Queue的算法:

将所有的pair<number, idx>存进pq
然后在从前向后loop中遇到一个后边比自己大的立即进行交换而得到结果

class Solution {
    public int maximumSwap(int num) {
        String numStr = String.valueOf(num);
        int N = numStr.length();
        int[] numArr = new int[N];

        for (int i = 0; i < N; ++i) {
            numArr[i] = numStr.charAt(i) - '0';
        }

        // 核心代码开始
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(
            (Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) -> {
                if (p1.getKey() == p2.getKey()) {
                    return p1.getValue() - p2.getValue();
                } else {
                    return p2.getKey() - p1.getKey();
                }
        });

        for (int i = 0; i < numArr.length; ++i) {
            System.out.println(numArr[i] + "," + i);
            pq.add(new Pair(numArr[i], i));
        }

        for (int i = 0; i < numArr.length; ++i) {
            var topValue = pq.poll();
            if (topValue.getValue() == i) {
                continue;
            }

            int j = topValue.getValue();
            int tmp = numArr[i];
            numArr[i] = topValue.getKey();
            numArr[j] = tmp;
            break;
        }
        // 核心代码结束

        int result = 0;
        int acc = 1;
        for (int i = numArr.length - 1; i >= 0; --i) {
            result += numArr[i] * acc;
            acc *= 10;
        }

        return result;
    }
}

注意这里的pq先以数字从大到小排序，当大小相同时，再以index前后排序。

如下所示，

1993
[(9,1), (9,2), (3,3), (1,0)]

98368
[(9,0), (8,1), (8,4), (6,3), (3,2)]

这里就开始有了个严重的问题，index的排序可以选择小的在前，大的在后(上例)，或者相反。

但是小的在前_1993_就不work，大的在前_98368_就不work。

核心的问题在于单纯依赖于pq存的index是没法满足要求的，但是这里也只需要额外的check 一下pq上的最大是在自己前面还是后面，前面的话自然是不能swap的，skip掉就好。

扣了一小时居然也给pq弄work了，如下:

class Solution {
    public int maximumSwap(int num) {
        String numStr = String.valueOf(num);
        int N = numStr.length();
        int[] numArr = new int[N];

        for (int i = 0; i < N; ++i) {
            numArr[i] = numStr.charAt(i) - '0';
        }

        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(
            (Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) -> {
                if (p1.getKey() == p2.getKey()) {
                    return p2.getValue() - p1.getValue();
                } else {
                    return p2.getKey() - p1.getKey();
                }
        });

        for (int i = 0; i < numArr.length; ++i) {
            pq.add(new Pair(numArr[i], i));
        }

        int cur = 0;
        while (cur < numArr.length && !pq.isEmpty()) {
            var nextLargest = pq.peek();
            var nextLargestIdx = nextLargest.getValue();
            var nextLargestValue = nextLargest.getKey();

            if (nextLargestIdx == cur) {
                pq.poll();
                continue;
            }

            if (nextLargestValue > numArr[cur]) {
                if (nextLargestIdx < cur) {
                    pq.poll();
                    continue;
                } else {
                    swap(numArr, cur, nextLargestIdx);
                    break;
                }
            }

            cur++;
        }

        return arrToNum(numArr);
    }

    void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    int arrToNum(int[] numArr) {
        int result = 0;
        int acc = 1;
        for (int i = numArr.length - 1; i >= 0; --i) {
            result += numArr[i] * acc;
            acc *= 10;
        }

        return result;
    }
}

这里Java和c++的默认pq implementation是不一样的，很坑。

换个角度

那么这里为什么说要换个角度呢，就是这题的简单解法来自于从_后向前iterate_。

从右往左一直记录最大值
直到数字不在递增
找到最左边可以与最大值交换的数字
交换即可

class Solution {
    public int maximumSwap(int num) {
        String numStr = String.valueOf(num);
        int N = numStr.length();
        int[] numArr = new int[N];

        for (int i = 0; i < N; ++i) {
            numArr[i] = numStr.charAt(i) - '0';
        }

        int maxValue = 0;
        int maxPos = -1;
        int minPos = -1;
        int rightIndex = -1;
        for (int i = numArr.length - 1; i >= 0; i--) {
            if (numArr[i] > maxValue) {
                maxValue = numArr[i];
                maxPos = i;
                continue;
            }

            if (numArr[i] < maxValue) {
                minPos = i;

                rightIndex = maxPos; // 重要，让rightIndex不在移动
            }
        }

        if (minPos == -1) return arrToNum(numArr);

        swap(numArr, rightIndex, minPos);
        return arrToNum(numArr);
    }

    void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    int arrToNum(int[] numArr) {
        int result = 0;
        int acc = 1;
        for (int i = numArr.length - 1; i >= 0; --i) {
            result += numArr[i] * acc;
            acc *= 10;
        }

        return result;    
    }
}

结语

花费了这么久时间，这题其实挺烂的。唯一值得学习的可能就是，时不时要换个角度，从后向前看。

最搞笑的是，写来写去，brutal force的解法在leetcode上是最快的。