[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，代码如下：