670 最大交换（找规律）

快来打我* 2022-09-02 11:37 194阅读 0赞

**1. 问题描述：**

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

**示例 1 :**

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

**示例 2 :**

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

**注意:**

给定数字的范围是 \[0, 10 ^ 8\]非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/maximum-swap

**2. 思路分析：**

这道题目类似于之前的下一个排列的（next\_permutation）题目，对于这种题目我们先画画图，可以发现当数字为降序的时候内部之间是无法通过调整顺序使得交换之后的数字是更大的，所以我们需要找到第一个升序的位置，当存在升序序列的时候交换右边升序的某个数字与左边的某个数字那么就一定可以使得整个数字是变得更大的，所以需要解决两个问题，第一个是选择右边升序位置的哪个数字，第二个是选择左边哪一个数字，右边的数字肯定是越大越好，所以我们应该选择右边最大的那个数字（相等的时候那么应该交换的是越低位的那个因为这样可以使得低位更小一点），因为我们需要使得交换之后数字越大那么我们应该从高位开始枚举，找到左边第一个小于右边最大数字的那个，交换这两个数字返回对应的整数即可。如果整个数字都是逆序的那么直接返回当前的数字即可，因为在循环中根本找不到这样的升序序列。

![20210803085628779.png][]

**3. 代码如下：**

class Solution:
        def maximumSwap(self, num: int) -> int:
            # 将整数num变为列表
            s = list(str(num))
            n = len(s)
            for i in range(n - 1):
                # 说明找到了升序的序列
                if s[i] < s[i + 1]:
                    k = i + 1
                    # 寻找右边大于等于s[i + 1]的位置
                    for j in range(k, n):
                        if s[j] >= s[k]: k = j
                    # 从前往后找第一个小于右边的位置找到之后交换对应的数字返回即可
                    for j in range(n):
                        if s[j] < s[k]:
                            s[j], s[k] = s[k], s[j]
                            return int("".join(s))
            # 当前数字全为逆序所以返回原来的数字即可
            return num

[20210803085628779.png]: /images/20220829/dcddd8aa7ea24fbaab7c6440c34f0546.png