title
Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.
Example 1:
Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.
Example 2:
Input: 9973
Output: 9973
Explanation: No swap.
solution
交换两个数，使它最大。
记录每个位置从右向左的max(i)， 当s[i]>max(i)使，交换
class Solution {
public:
int maximumSwap(int num) {
string s = to_string(num);
int t='0';
int index = 0;
unordered_map<int, pair<int, int>> map1;
for (int i = s.length() - 1; i >= 0; i--) {
if (s[i] > t) {
t = s[i];
index = i;
}
map1[i] = make_pair(t,index);
}
for (int i = 0; i < s.length(); i++) {
if (s[i] < map1[i].first) {
swap(s[i], s[map1[i].second]);
break;
}
}
return stoi(s);
}
};