LeetCode 670. 最大交换

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

示例 2 :
输入: 9973
输出: 9973
解释: 不需要交换。
注意:
给定数字的范围是 [0, 10^8]

class Solution {
public:
    int maximumSwap(int num) {
    	string s = to_string(num);
    	int i, n = s.size(), maxnum = -1, maxid;
    	vector<int> rightMaxidx(n,-1);
    	for(i = n-1; i >= 0; --i)
    	{
    		if(s[i]-'0' > maxnum)
    		{
    			maxnum = s[i]-'0';
    			maxid = i;
    		}
    		rightMaxidx[i] = maxid;
    	}
    	for(i = 0; i < n; ++i)
    	{
    		if(rightMaxidx[i] == i || s[i] == s[rightMaxidx[i]])
    			continue;
    		swap(s[i],s[rightMaxidx[i]]);
    		break;
    	}
    	return stoi(s);
    }
};