31.下一个数列

题目
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题意分析

如果一个排列为A，下一个排列为A_NEXT，那么A_NEXT一定与A有尽可能长的公共前缀。

看具体例子，一个排列为124653，如何找到它的下一个排列，因为下一个排列一定与124653有尽可能长的前缀，所以，脑洞大开一下，从后面往前看这个序列，如果后面的若干个数字有下一个排列，问题就得到了解决。

第一步：找最后面1个数字的下一个全排列。

124653，显然最后1个数字3不具有下一个全排列。

第二步：找最后面2个数字的下一个全排列。

124653，显然最后2个数字53不具有下一个全排列。

第三步：找最后面3个数字的下一个全排列。

124653，显然最后3个数字653不具有下一个全排列。

------插曲：到这里相信大家已经看出来，如果一个序列是递减的，那么它不具有下一个排列。

第四步：找最后面4个数字的下一个全排列。

124653，我们发现显然最后4个数字4653具有下一个全排列。因为它不是递减的，例如6453，5643这些排列都在4653的后面。

我们总结上面的操作，并总结出重复上面操作的两种终止情况：

1：从后向前比较相邻的两个元素，直到前一个元素小于后一个元素，停止

2：如果已经没有了前一个元素，则说明这个排列是递减的，所以这个排列是没有下一个排列的。

124653这个排列终止情况是上面介绍的第一种，从后向前比较相邻的2个元素，遇到4<6的情况停止。

并且我们可以知道：

1：124653和它的下一个排列的公共前缀为12(因为4653存在下一个排列，所以前面的数字12保持不变)

2：4后面的元素是递减的(上面介绍的终止条件是前一个元素小于后一个元素，这里是4<6)

现在，我们开始考虑如何找到4653的下个排列，首先明确4后面的几个数字中至少有一个大于4.

4肯定要和653这3个数字中大于4的数字中(6，5)的某一个进行交换。这里就是4要和6，5中的某一个交换，很明显要和5交换，如果找到这样的元素呢，因为我们知道4后面的元素是递减的，所以在653中从后面往前查找，找到第一个大于4的数字，这就是需要和4进行交换的数字。这里我们找到了5，交换之后得到的临时序列为5643.，交换后得到的643也是一个递减序列。

所以得到的4653的下一个临时序列为5643，但是既然前面数字变大了(4653--->5643)，后面的自然要变为升序才行，变换5643得到5346.

所以124653的下一个序列为125346.

看一个permutation，比如

125430

从末尾开始，找到decreasing subsequence，5430，因为来调5330无论怎么调，都不可能有比它更小的，数也被自然的分成两部分(1,2) 和（5，4，3，0)
下一步是找这个sequence里面第一个比前面部分，比2大的，3，也很容易理解，因为下一个必定是(1,3)打头
交换 3和2 ，变成 (1,3,5,4,2,0),再把后面的部分reverse，得到后面部分可得到的最小的
这个时候，得到下一个sequence 130245`

作者：冰源
链接：https://www.jianshu.com/p/092ce62c87ef
來源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。

思路
暴力法，从后向前搜索，直到出现满足交换的数。

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        for(int i = nums.size() -1; i >= 0; i --)
        {
            for (int j = nums.size() - 1; j > i; j --)
            {
                if (nums[i] < nums[j])
                {
                    swap(nums[i], nums[j]);
                    sort(nums.begin() +i+1, nums.end());
                    return;
                }
            }
        }
        reverse(nums.begin(), nums.end());
    }
};

int main(int argc, char* argv[])
{
    vector<int> test = {1, 3, 2};
    Solution().nextPermutation(test);
    system("pause");
    return 0;
}