# 670. Maximum Swap

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.
``````

Note:

1. The given number is in the range [0, 108]

``````class Solution {
public:
int maximumSwap(int num) {
string str = to_string(num);
int res = num, n = str.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
swap(str[i], str[j]);
res = max(res, stoi(str));
swap(str[i], str[j]);
}
}
return res;
}
};
``````

1 9 9 3

9 9 9 3  (back数组)

9 9 1 3

``````class Solution {
public:
int maximumSwap(int num) {
string res = to_string(num), back = res;
for (int i = back.size() - 2; i >= 0; --i) {
back[i] = max(back[i], back[i + 1]);
}
for (int i = 0; i < res.size(); ++i) {
if (res[i] == back[i]) continue;
for (int j = res.size() - 1; j > i; --j) {
if (res[j] == back[i]) {
swap(res[i], res[j]);
return stoi(res);
}
}
}
return stoi(res);
}
};
``````

``````class Solution {
public:
int maximumSwap(int num) {
string str = to_string(num);
vector<int> buckets(10, 0);
for (int i = 0; i < str.size(); ++i) {
buckets[str[i] - '0'] = i;
}
for (int i = 0; i < str.size(); ++i) {
for (int k = 9; k > str[i] - '0'; --k) {
if (buckets[k] <= i) continue;
swap(str[i], str[buckets[k]]);
return stoi(str);
}
}
return num;
}
};
``````

``````class Solution {
public:
int maximumSwap(int num) {
string str = to_string(num);
int n = str.size(), mx = n - 1, pos1 = -1, pos2 = -1;
for (int i = n - 2; i >= 0; --i) {
if (str[i] < str[mx]) {
pos1 = i;
pos2 = mx;
} else if (str[i] > str[mx]) {
mx = i;
}
}
if (pos1 != -1) swap(str[pos1], str[pos2]);
return stoi(str);
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/670

Create Maximum Number

https://leetcode.com/problems/maximum-swap/

https://leetcode.com/problems/maximum-swap/discuss/107068/Java-simple-solution-O(n)-time

https://leetcode.com/problems/maximum-swap/discuss/107153/simple-c-using-stdstring-and-stdstoi

https://leetcode.com/problems/maximum-swap/discuss/107084/C%2B%2B-3ms-O(n)-time-O(n)-space-DP-solution

https://leetcode.com/problems/maximum-swap/discuss/107073/C%2B%2B-one-pass-simple-and-fast-solution%3A-1-3ms-O(n)-time

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation