力扣HOT100之技巧：31. 下一个排列

这道题本来想直接暴力回溯的，但是想了下还是算了，自己想这个思路完全想不出来，直接去看灵神的题解了，感觉还是很好懂的，强烈推荐去看看他的题解。
我们先讨论最一般的情况：对于一组排列，我们要找到它的下一个排列，就需要从右往左遍历，找到第一个小于右边相邻元素的位置。例如，对于排列[3, 5, 1, 4, 2, 6, 1]，我们要找下一个大于当前数的排列(nums[i] < nums[i + 1])，我们就需要找到元素2的位置i，它是从右往左数，第一个小于右边相邻元素的数，此时我们还不能简单地将2和6简单交换位置就草草了事，因为如果输入是[3, 5, 1, 4, 2, 6, 0]，将2和6交换位置将得到[3, 5, 1, 4, 6, 2, 0]，显然，下一个排列应当为[3, 5, 1, 4, 6, 0, 2]。因此，在找到i之后，我们可以得到如下性质：从i + 1到数组的最后一个元素，这段数字应当是降序排列的，这是因为i是从右往左数第一个小于右侧相邻元素的值，从i + 1到数组的倒数第二个元素，每一个元素都大于等于右边相邻的元素，从而形成降序排列。我们还需要寻找一个元素nums[j],使得nums[j]恰好为大于nums[i]的元素中的最小值，从右往左数，第一个大于nums[i]的元素就是nums[j],对于输入[3, 5, 1, 4, 2, 6, 0]，nums[i] == 2，nums[j] == 6，我们将其位置交换得到[3, 5, 1, 4, 6, 2, 0]。此时还没有得到下一个排列，因为[i + 1, end)这个区间是降序排列的，我们仍需要对其进行逆转为升序排列使其变得更小，最终得到下一个排列，因此我们通过reverse(nums.begin() + i + 1, nums.end());来实现反转，从而得到下一个排列。
下面再来讨论特殊情况，当原排列已经是最大的排列，不可能得到更大的排列时，我们需要将其转化为最小的排列，最大的排列一定是从头到尾都降序排列，我们将其逆转，得到升序排列，此时一定是最小的排列。
综上所述，如果我们能找到符合条件的i，那么我们还需要进行第二步操作，找到符合条件的j，进行交换，如果找不到，就直接执行第三步操作。第三步，将指定范围内的排列逆序。最终得到下一个排列。

class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size();//1.从右往左寻找第一个小于右侧相邻元素的数int i = n - 2;while(i >= 0 && nums[i] >= nums[i + 1])i--;//2.如果找到了，那么一定满足i >= 0,如果不满足，则跳过第2步//此时从i + 1到末尾一定是单调递减的，因为i是从右往左数第一个小于右侧相邻元素的值if(i >= 0){int j = n - 1;while(nums[j] <= nums[i])j--;swap(nums[i], nums[j]);   //交换i和j的位置，数值已经变大，但是可能不是最接近原数的下一个排列}//3.如果存在对应的i，则此阶段需要进行最后的微调，由于[i + 1, end)这个区间是降序排列的//我们仍需要对其进行逆转为升序排列使其变得更小//如果没有找到合适的i，则说明原来的排列已经是最大值，我们需要将其逆序排列得到最小值reverse(nums.begin() + i + 1, nums.end());}
};