Medium

题目描述

给你一个整数 num，你最多可以交换两个数字一次来获得最大值的数字。

返回你能得到的最大值数字。

示例 1：

输入：num = 2736
输出：7236
解释：交换数字 2 和数字 7。

示例 2：

输入：num = 9973
输出：9973
解释：无需交换。

提示：

  • 0 <= num <= 10^8

解题思路

这道题的核心思路是贪心算法。我们要找到能让数字变得最大的最优交换位置。

基本思路：

  1. 将数字转换为字符数组，方便操作每一位
  2. 从左到右遍历，对于每一位，我们希望找到它右边最大的数字来替换它
  3. 如果找到了比当前位更大的数字，我们要选择最大的那个，且位置尽可能靠右（保证交换后字典序最大）

具体算法：

  1. 记录每个数字最后出现的位置，这样当有多个相同的最大值时，我们选择最右边的
  2. 从左到右遍历每一位，检查是否存在比当前位大的数字在后面
  3. 一旦找到第一个可以改善的位置，立即进行交换并返回结果

为什么是贪心的： 因为我们总是优先处理高位，高位的改善对整体数值的提升最大。只要找到第一个可以改善的位置，就是最优解。

时间复杂度为 O(n)，其中 n 是数字的位数，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        int n = s.length();
        
        // 记录每个数字最后出现的位置
        vector<int> last(10, -1);
        for (int i = 0; i < n; i++) {
            last[s[i] - '0'] = i;
        }
        
        // 从左到右遍历，寻找第一个可以改善的位置
        for (int i = 0; i < n; i++) {
            // 从9到当前数字+1，查找是否有更大的数字在后面
            for (int d = 9; d > s[i] - '0'; d--) {
                if (last[d] > i) {
                    // 找到了，进行交换
                    swap(s[i], s[last[d]]);
                    return stoi(s);
                }
            }
        }
        
        return num;
    }
};

class Solution:
    def maximumSwap(self, num: int) -> int:
        s = list(str(num))
        n = len(s)
        
        # 记录每个数字最后出现的位置
        last = [-1] * 10
        for i in range(n):
            last[int(s[i])] = i
        
        # 从左到右遍历，寻找第一个可以改善的位置
        for i in range(n):
            # 从9到当前数字+1，查找是否有更大的数字在后面
            for d in range(9, int(s[i]), -1):
                if last[d] > i:
                    # 找到了，进行交换
                    s[i], s[last[d]] = s[last[d]], s[i]
                    return int(''.join(s))
        
        return num

public class Solution {
    public int MaximumSwap(int num) {
        char[] chars = num.ToString().ToCharArray();
        int n = chars.Length;
        
        // 记录每个数字最后出现的位置
        int[] last = new int[10];
        Array.Fill(last, -1);
        for (int i = 0; i < n; i++) {
            last[chars[i] - '0'] = i;
        }
        
        // 从左到右遍历，寻找第一个可以改善的位置
        for (int i = 0; i < n; i++) {
            // 从9到当前数字+1，查找是否有更大的数字在后面
            for (int d = 9; d > chars[i] - '0'; d--) {
                if (last[d] > i) {
                    // 找到了，进行交换
                    char temp = chars[i];
                    chars[i] = chars[last[d]];
                    chars[last[d]] = temp;
                    return int.Parse(new string(chars));
                }
            }
        }
        
        return num;
    }
}

/**
 * @param {number} num
 * @return {number}
 */
var maximumSwap = function(num) {
    const chars = num.toString().split('');
    const n = chars.length;
    
    // 记录每个数字最后出现的位置
    const last = new Array(10).fill(-1);
    for (let i = 0; i < n; i++) {
        last[parseInt(chars[i])] = i;
    }
    
    // 从左到右遍历，寻找第一个可以改善的位置
    for (let i = 0; i < n; i++) {
        // 从9到当前数字+1，查找是否有更大的数字在后面
        for (let d = 9; d > parseInt(chars[i]); d--) {
            if (last[d] > i) {
                // 找到了，进行交换
                [chars[i], chars[last[d]]] = [chars[last[d]], chars[i]];
                return parseInt(chars.join(''));
            }
        }
    }
    
    return num;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n为数字的位数，遍历数字的每一位，内层循环最多10次
空间复杂度O(n)需要存储数字的字符数组和last数组

相关题目