LeetCode HOT100 - 下一个排列

考虑下一个排列应该是什么样的

下一个排列要变大，而且变大的应该尽量少

于是前缀应该尽可能不变，也就是调整的位置应该尽可能靠后

于是我们倒序去找，因为前缀不变，所以变的那个数字就是和后缀中大于它的数交换

所以就是后缀中存在大于它的数，这种情况下我们可以交换

因此不妨维护后缀最大值，这样当前元素小于那个最大值说明这个数可行

而交换为了增量减小，要交换大于它的最小值

而且交换完之后由于高位原则已经比原数要大了，所以剩下的元素排序即可

结合一下，那么不妨先给后缀排序，然后找 upper_bound ，找到的元素进行交换，因为大小关系是保证的，所以交换完后不需要再排序

class Solution {
public:void nextPermutation(vector<int>& a) {int n = a.size();int mx = a.back();for (int i =  n - 2; i >= 0; i--) {if (a[i] < mx) {reverse(a.begin() + i + 1, a.end());int it = upper_bound(a.begin() + i + 1, a.end(), a[i]) - a.begin();swap(a[it], a[i]);return;} else {mx = max(mx, a[i]);}}reverse(a.begin(), a.end());return;}
};