Daily LeetCode – day0046 0670. Maximum Swap

// 0670. Maximum Swap
class Solution {
    public int maximumSwap(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        int len = chars.length;
        int[] rightest = new int[]{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
        for (int i = len - 1; i >= 0; --i) {
            if (rightest[chars[i] - 48] == -1) {
                rightest[chars[i] - 48] = i;
            }
        }
        for (int i = 0; i < len; ++i) {
            for (int j = 9; j > chars[i] - 48; --j) {
                if (rightest[j] > i) {
                    chars[rightest[j]] = chars[i];
                    chars[i] = (char) (j + 48);
                    return Integer.parseInt(String.valueOf(chars));
                }
            }
        }
        return num;
    }
}
学习笔记:
这是一道非常经典的题目,如果使用双重循环比较尝试的话,复杂度极高。
应该从右往左找出每个数字最右边的一个。
然后从左往右找出第一个需要替换的数字。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注