31.下一个排列

        下一个排列是说,给你一个数组，求出按照字典序排列的下一个序列，什么意思呢？

例如，1 ，2，3。下一个排列是1，3，2。如果不清楚，我们继续看下一个例子

        1，3，5，4，2 他的下一个排列是1，4，2，3，5,怎么出来的呢？

既然要我们找按字典序排列更大的，那么下一个排列就比当前序列大一点点就好，如果我们有以下几个方案

        1，修改4 ，2，那么 1，3，5，2，4，比当前还要小，这不行

        2，修改5，4，2，因为5，4，2是降序的，修改哪一个位置，都会比当前小， 

        3，修改3，5，4，2，我们将3，改为 4，   1 4 _

下一个排列是指在字典序中，找到一个比当前序列稍大的新序列。以数列 1, 2, 3 为例，它的下一个排列是 1, 3, 2。

再比如数列 1, 3, 5, 4, 2，它的下一个排列是 1, 4, 2, 3, 5。这个结果是怎样得出的呢？

我们遵循"下一个排列仅比当前序列大一点点"的原则，尝试以下方案：

1. 如果修改 4 和 2，得到 1, 3, 5, 2, 4，这比原序列更小，不符合要求
2. 修改 5, 4, 2 也不行，因为这部分是降序排列，任何修改都会使序列更小
3. 修改 3, 5, 4, 2，将 3 替换为 4，得到 1, 4, _, _, _。此时我们找到了一个比原序列大的新序列，接下来只需将剩余部分按升序排列即可。

整个过程可以总结为以下步骤：

1. 从右向左扫描，找到第一个数字 x，满足其右侧存在比它更大的数字。这样可以使 x 变大。在 1, 3, 5, 4, 2 中，x=3。值得注意的是，x 右侧的序列必定是降序排列。如果右侧不是降序，就意味着存在比 x 更早满足条件的数字。

2. 在 x 的右侧找到第一个比 x 大的数字，交换这两个数字的位置。在本例中，就是交换 3 和 4。

3. 为保持"下一个排列仅比当前序列大一点点"的原则，将交换后 x 右侧的序列反转，使其成为升序排列（因为原先是降序，反转后即为最小字典序）。这样就得到了下一个排列。

_ _,找到了比当前大的序列，那么本着下一个排列就比当前序列大一点点就好的原则，后面的序列我们按照顺序排列即可。

        代码：

class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size();int i = n - 2;while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}if (i >= 0) {int j = n - 1;while (nums[j] <= nums[i]) {j--;}swap(nums[j],nums[i]);}reverse(nums.begin() + i + 1,nums.end());}
};

        时间复杂度：O(n),最坏情况下，序列是降序的，需要全部遍历

        空间复杂度：O(1)，仅使用了额外变量