LeetCode 670. 最大交换

Categories:

题目描述
思路分析
1. 解法一：贪心 + 记录末位索引（推荐）
相似题目

题目描述

✅ 670. 最大交换

思路分析

解法一：贪心 + 记录末位索引（推荐）

核心思路：

将整数转为字符数组，对每个数字（0-9）记录其在数组中最后出现的位置。

从高位到低位扫描，对当前位的数字，尝试在其后面找一个更大的数字（从 9 往下枚举到当前值+1）。

若找到，则交换这两位，立刻返回结果（只做一次交换）。

关键点：使用”最后出现位置”而非”第一次出现位置”，是为了确保交换的是最靠右的较大数字，从而使高位增益最大。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数字的位数（最多 10 位），遍历一次建表，再遍历一次扫描。

空间复杂度：O(n)，存储字符数组与末位索引数组（固定大小 10）。

class Solution {
    public int maximumSwap(int num) {
        // 将数字转为字符数组，方便按位操作
        char[] digits = Integer.toString(num).toCharArray();
        int n = digits.length;

        // 记录每个数字（0-9）最后出现的位置
        int[] last = new int[10];
        for (int i = 0; i < n; i++) {
            last[digits[i] - '0'] = i;
        }

        // 从高位到低位扫描
        for (int i = 0; i < n; i++) {
            // 从 9 往下找是否存在比当前位更大且在其右边的数字
            for (int d = 9; d > digits[i] - '0'; d--) {
                if (last[d] > i) {
                    // 找到后交换，直接返回结果
                    char tmp = digits[i];
                    digits[i] = digits[last[d]];
                    digits[last[d]] = tmp;
                    return Integer.parseInt(new String(digits));
                }
            }
        }

        // 无需交换，原数已是最大
        return num;
    }
}

func maximumSwap(num int) int {
    // 将数字转为字节切片，方便按位操作
    digits := []byte(strconv.Itoa(num))
    n := len(digits)

    // 记录每个数字（0-9）最后出现的位置
    last := [10]int{}
    for i := 0; i < n; i++ {
        last[digits[i]-'0'] = i
    }

    // 从高位到低位扫描
    for i := 0; i < n; i++ {
        // 从 9 往下找是否存在比当前位更大且在其右边的数字
        for d := 9; d > int(digits[i]-'0'); d-- {
            if last[d] > i {
                // 找到后交换，直接返回结果
                digits[i], digits[last[d]] = digits[last[d]], digits[i]
                result, _ := strconv.Atoi(string(digits))
                return result
            }
        }
    }

    // 无需交换，原数已是最大
    return num
}

相似题目

题目	难度	考察点
31. 下一个排列	中等	贪心、数组
179. 最大数	中等	贪心、排序
321. 拼接最大数	困难	贪心、单调栈
402. 移掉 K 位数字	中等	贪心、单调栈
1663. 具有给定数字总和的最小字符串	中等	贪心、字符串
2231. 按奇偶性交换后的最大数字	简单	贪心、排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/68769992