最大交换

670. 最大交换

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。

注意:

给定数字的范围是 [0, 10⁸]

相似题目

拼接最大数

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maximumSwap(int num) { } };

javascript 解法, 执行用时: 55 ms, 内存消耗: 49.1 MB, 提交时间: 2024-01-22 09:35:49

/**
 * @param {number} num
 * @return {number}
 */
var maximumSwap = function(num) {
    const charArray = [...'' + num];
    const n = charArray.length;
    let maxIdx = n - 1;
    let idx1 = -1, idx2 = -1;
    for (let i = n - 1; i >= 0; i--) {
        if (charArray[i] > charArray[maxIdx]) {
            maxIdx = i;
        } else if (charArray[i] < charArray[maxIdx]) {
            idx1 = i;
            idx2 = maxIdx;
        }
    }
    if (idx1 >= 0) {
        swap(charArray, idx1, idx2);
        return parseInt(charArray.join(''));
    } else {
        return num;
    }
}

/**
 * @param {number} num
 * @return {number}
 */
var maximumSwap2 = function(num) {
    const charArray = [...'' + num];
    const n = charArray.length;
    let maxNum = num;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            swap(charArray, i, j);
            maxNum = Math.max(maxNum, parseInt(charArray.join('')));
            swap(charArray, i, j);
        }
    }
    return maxNum;
}

const swap = (charArray, i, j) => {
    const temp = charArray[i];
    charArray[i] = charArray[j];
    charArray[j] = temp;
};

cpp 解法, 执行用时: 0 ms, 内存消耗: 7.2 MB, 提交时间: 2024-01-22 09:34:50

class Solution {
public:
    // 直接遍历
    int maximumSwap(int num) {
        string charArray = to_string(num);
        int n = charArray.size();
        int maxNum = num;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(charArray[i], charArray[j]);
                maxNum = max(maxNum, stoi(charArray));
                swap(charArray[i], charArray[j]);
            }
        }
        return maxNum;
    }

    // 贪心
    int maximumSwap2(int num) {
        string charArray = to_string(num);
        int n = charArray.size();
        int maxIdx = n - 1;
        int idx1 = -1, idx2 = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (charArray[i] > charArray[maxIdx]) {
                maxIdx = i;
            } else if (charArray[i] < charArray[maxIdx]) {
                idx1 = i;
                idx2 = maxIdx;
            }
        }
        if (idx1 >= 0) {
            swap(charArray[idx1], charArray[idx2]);
            return stoi(charArray);
        } else {
            return num;
        }
    }
};

java 解法, 执行用时: 0 ms, 内存消耗: 38.2 MB, 提交时间: 2023-06-12 16:28:10

// 贪心
class Solution {
    public int maximumSwap(int num) {
        char[] charArray = String.valueOf(num).toCharArray();
        int n = charArray.length;
        int maxIdx = n - 1;
        int idx1 = -1, idx2 = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (charArray[i] > charArray[maxIdx]) {
                maxIdx = i;
            } else if (charArray[i] < charArray[maxIdx]) {
                idx1 = i;
                idx2 = maxIdx;
            }
        }
        if (idx1 >= 0) {
            swap(charArray, idx1, idx2);
            return Integer.parseInt(new String(charArray));
        } else {
            return num;
        }
    }

    public void swap(char[] charArray, int i, int j) {
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
    }
}

java 解法, 执行用时: 1 ms, 内存消耗: 38.1 MB, 提交时间: 2023-06-12 16:27:50

// 直接遍历
class Solution {
    public int maximumSwap(int num) {
        char[] charArray = String.valueOf(num).toCharArray();
        int n = charArray.length;
        int maxNum = num;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(charArray, i, j);
                maxNum = Math.max(maxNum, Integer.parseInt(new String(charArray)));
                swap(charArray, i, j);
            }
        }
        return maxNum;
    }

    public void swap(char[] charArray, int i, int j) {
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
    }
}

python3 解法, 执行用时: 32 ms, 内存消耗: 15.9 MB, 提交时间: 2023-06-12 16:27:30

# 直接遍历
class Solution:
    def maximumSwap(self, num: int) -> int:
        ans = num
        s = list(str(num))
        for i in range(len(s)):
            for j in range(i):
                s[i], s[j] = s[j], s[i]
                ans = max(ans, int(''.join(s)))
                s[i], s[j] = s[j], s[i]
        return ans

python3 解法, 执行用时: 48 ms, 内存消耗: 16 MB, 提交时间: 2023-06-12 16:27:13

# 贪心
class Solution:
    def maximumSwap(self, num: int) -> int:
        s = list(str(num))
        n = len(s)
        maxIdx = n - 1
        idx1 = idx2 = -1
        for i in range(n - 1, -1, -1):
            if s[i] > s[maxIdx]:
                maxIdx = i
            elif s[i] < s[maxIdx]:
                idx1, idx2 = i, maxIdx
        if idx1 < 0:
            return num
        s[idx1], s[idx2] = s[idx2], s[idx1]
        return int(''.join(s))

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-12 16:26:38

// 贪心
func maximumSwap(num int) int {
    s := []byte(strconv.Itoa(num))
    n := len(s)
    maxIdx, idx1, idx2 := n-1, -1, -1
    for i := n - 1; i >= 0; i-- {
        if s[i] > s[maxIdx] {
            maxIdx = i
        } else if s[i] < s[maxIdx] {
            idx1, idx2 = i, maxIdx
        }
    }
    if idx1 < 0 {
        return num
    }
    s[idx1], s[idx2] = s[idx2], s[idx1]
    v, _ := strconv.Atoi(string(s))
    return v
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-12 16:26:16

// 直接遍历
func maximumSwap(num int) int {
    ans := num
    s := []byte(strconv.Itoa(num))
    for i := range s {
        for j := range s[:i] {
            s[i], s[j] = s[j], s[i]
            v, _ := strconv.Atoi(string(s))
            ans = max(ans, v)
            s[i], s[j] = s[j], s[i]
        }
    }
    return ans
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-12 16:25:49

func maximumSwap(num int) int {
    chars, stack := []byte(strconv.Itoa(num)), []int{}
    n := len(chars)
    left, right := n, n
    for i, c := range chars {
        for len(stack) > 0 && chars[stack[len(stack) - 1]] < c {
            idx := stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            if idx < left {
                left, right = idx, i
            }
            if idx == right {
                right = i
            }
        }
        if right < n && chars[right] == c {
            right = i
        }
        stack = append(stack, i)
    }
    if left < n {
        chars[left], chars[right] = chars[right], chars[left]
        ans, _ := strconv.Atoi(string(chars))
        return ans
    }
    return num
}

java 解法, 执行用时: 1 ms, 内存消耗: 38.2 MB, 提交时间: 2023-06-12 16:25:17

class Solution {
    public int maximumSwap(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        int n = chars.length;
        int left = n, right = n;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && chars[stack.peekLast()] < chars[i]) {
                int idx = stack.removeLast();
                if (idx < left) {
                    left = idx;
                    right = i;
                }
                if (idx == right) {
                    right = i;
                }
            }
            if (right < n && chars[right] == chars[i]) {
                right = i;
            }
            stack.addLast(i);
        }
        if (left < n) {
            char tmp = chars[left];
            chars[left] = chars[right];
            chars[right] = tmp;
            return Integer.parseInt(new String(chars));
        }
        return num;
    }
}

python3 解法, 执行用时: 40 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-12 16:24:59

class Solution:
    def maximumSwap(self, num: int) -> int:
        s, stack, left, right = str(num), [], None, None
        for i, c in enumerate(s):
            while stack and s[stack[-1]] < c:
                idx = stack.pop()
                if left is None or idx < left:
                    left, right = idx, i
                if idx == right:
                    right = i
            if right is not None and c == s[right]:
                right = i
            stack.append(i)
        return int(s[:left] + s[right] + s[left+1:right] + s[left] + s[right+1:]) if left is not None else num

上一题

下一题

详情