题目
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736 输出: 7236 解释: 交换数字2和数字7。
示例 2 :
输入: 9973 输出: 9973 解释: 不需要交换。
解题
方法一：贪心
贪心：从头遍历，找到右侧一个比它大，且值最大的数。
比如2734， 在2的右边最大是7，因此交换结果7234
又比如27734，在2的右边最大是7，那么要交换最后一个7才能保证最大，结果为77234
因此使用maxRight记录当前索引，右侧最大的数
class Solution { public: int maximumSwap(int num) { string s=to_string(num); int n=s.size(); vector<int> maxRight(n); char maxnum=-1; for(int i=n-1;i>=0;i--){ maxnum=max(maxnum,s[i]); maxRight[i]=maxnum; } for(int i=0;i<n;i++){ if(s[i]<maxRight[i]){ int j=n-1; while(j>0&&s[j]!=maxRight[i]) j--; swap(s[i],s[j]); return stoi(s); } } return num; } };
