难度中等354
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736
输出: 7236
解释: 交换数字2和数字7。示例 2 :
输入: 9973
输出: 9973
解释: 不需要交换。注意:
- 给定数字的范围是 [0, 108]
思路：
考虑最优解：容易看出，尽量使最前面的数最大，是最好的结果。也就是说，如果后面的最大值比第一个数大，就将它和第一个数交换并返回答案；否则考虑第二个数……如果到最后发现已经是倒序排列了，就不做交换，直接返回。
其实，这不就是选择排序的过程嘛！依次找到最大的数、次大的数……并与第一个数、第二个数……交换。不同的是，我们最多只能执行一次交换。所以，我们套用选择排序的模板，如果执行了交换就直接返回。
值得注意的是，内层循环应当从后往前进行，这是因为在有两个最大值时，使用后面的更好。
- 【贪心】
- 贪心法一句话总结：每一位数字应该不小于所有排它后面的数字，否则找最大的且排最后面的数字与之交换直观看就是，寻找第一个上升位置之后的最大数位置，并尽量与前面的数互换，互换的原则是：比自己小
class Solution {
public:
int maximumSwap(int num) {
string tmp = to_string(num);//转成字符串
for(int i = 0;i < tmp.size(); ++i)//选择排序模板
{
int pos = i;
for(int j = tmp.size() - 1; j > i; --j)//内层循环从后往前
if(tmp[pos] < tmp[j])
pos = j;
if(pos != i)//如果最大的不是i，交换并返回
{
swap(tmp[i], tmp[pos]);
return stoi(tmp);
}
}
return num;//倒序排列，直接返回
}
};