670.最大交换

https://leetcode.cn/problems/maximum-swap/solution/by-qingfengpython-yjti/

难度：中等

标签: Python Java 暴力栈指针

题目：

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

注意：给定数字的范围是 [0, 10 ^ 8]

示例：

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

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

分析

这道题虽然现实数字范围在 0 - 10 ^ 8, 看似很大，但其实最多只有9位…
思路一: 暴力
我们可以通过将数字转化为数组的方式进行双层for循环的暴力比较快速通过。

但是举一反三，如果题目给我们的是一个10 ^ 8 的数组，让我们只交换一次变成拼接后更大的数组呢？
此时通过暴力解法肯定是会AW的！
所以我们需要考虑其他的解题方式：

通过暴力的方式，我们了解到，只要排在后面的数字比排在前面的数字大，就满足两两交换的条件。
并且应该将尽量将排在最后且更大的数字，替换排在最前且更小的数字才能使得结果更大。
下面再来说两种解题思路：
思路二: 数字的单调性
什么情况下无需交换？数字的后一位总是小于等于前一位的情况，就是说是单调的。
那么是否可以考虑：

通过数字的单调性，满足单调性的部分
遍历剩余部分找到最大的数值
通过弹栈的方式获取最大可替换的数字进行交换，最终获取结果

这种思想，比较符合我们正向的思维方式，并且保持了时间复杂度的要求。
但由于场景过程较多，代码上不算简洁。

思路三: 倒序查找
下面说下倒序查找的方式。
在思路二的编码过程中，我们最终弹栈的方式，是一个逆向的操作，那么查找最值也是可以通过逆向遍历来实现的。
所以，转化一下思路：

采用逆向遍历的方式，初始化左端点、又断点、最大值三个指针均为列表的最后一个下标
在遍历过程中，将每次遍历的数字与最大值下标p进行比较更新
当遇到逆向的当前数字比前一个数字小时，满足交换条件交换，此时更新左端点，并将右端点更新为当前最大值下标p

重复2、3过程，直到结束即可。

下面来看看三种思路的解题代码：

解题：

思路一：

class Solution:
    def maximumSwap(self, num: int) -> int:
        ret = num
        s = str(num)
        for i in range(0, len(s)):
            for j in range(i + 1, len(s)):
                if s[j] > s[i]:
                    tmp = list(s)
                    tmp[i], tmp[j] = tmp[j], tmp[i]
                    ret = max(int(''.join(tmp)), ret)
        return ret

思路二：

class Solution:
    def maximumSwap(self, num: int) -> int:
        n = list(str(num))
        lg = len(n)
        stack = [0]
        r = 0
        for i in range(lg - 1):
            if n[i] < n[stack[-1]]:
                stack.append(i)
            if n[i] < n[i + 1]:
                r = i + 1
                break
        if r == 0:
            return num
        for j in range(r, len(n)):
            if n[j] >= n[r]:
                r = j
        l = stack[-1]
        while stack and n[stack[-1]] < n[r]:
            l = stack.pop()
        n[l], n[r] = n[r], n[l]
        return int(''.join(n))

思路三：

class Solution:
    def maximumSwap(self, num: int) -> int:
        n = list(str(num))
        lg = len(n)
        l = r = p = lg - 1
        for i in range(lg - 2, -1, -1):
            if n[i] > n[p]:
                p = i
            elif n[i] < n[p]:
                l, r = i, p
        n[l], n[r] = n[r], n[l]
        return int(''.join(n))