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))
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
有喜欢力扣刷题的小伙伴可以加我微信（King_Uranus）互相鼓励，共同进步，一起玩转超级码力！
我的个人博客：https://qingfengpython.cn