670.最大交换 暴力、单调栈、指针的逆序遍历 三种解题思路。

670.最大交换

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

难度：中等

标签: Python Java 暴力 栈 指针

题目：

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

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

示例：

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

示例 2:
输入: 9973
输出: 9973
解释: 不需要交换。
1
2
3
4
5
6
7
8
9

分析

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

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

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

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

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

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

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

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

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

解题：

思路一：

class Solution:
    def maximumSwap(self, num: int) -> int:
        ret = num
        s = str(num)
        for i in range(
1
2
3
4