[LeetCode]Maximum Swap

这道题只能交换一次，找交换之后的最大值，本质上就是找一对reverse pair，满足下面两个条件：

• reverse pair的第一个数越往前/左越好
• 满足第一个条件前提下，reverse pair的第二个数越大越好，有相同的数的话取更靠右边的数

找这对pair有很多种方法，brute force的话n^2可以找到。我们从左边找的话，找到第一个reverse pair后，需要维护pair第二个数的最大值，并且向左不断更新pair的第一个数。当然如果我们从尾到头遍历会更好找这一对pair，一直维护第二的数的最大值，同时如果当前数存在reverse pair，将其设为pair的第一个数。一次遍历即可，linear time，constant space，代码如下：

	class Solution {
	public:
	int maximumSwap(int num) {
	string s = to_string(num);
	int len = s.size(), l = -1, r = len - 1;
	pair<int, int> p(-1, -1);
	for(int i = len - 2; i >= 0; --i)
	{
	if(s[i] > s[r])r = i;
	if(s[i] < s[r])
	{
	l = i;
	p = {l, r};
	}
	}
	if(p.first >= 0)
	swap(s[p.first], s[p.second]);
	return stoi(s);
	}
	};

view raw Maximum Swap.cpp hosted with ❤ by GitHub