计算机低能儿从0刷leetcode | 31.下一个排列

题目：31. 下一个排列

思路：

本题中，我们需要寻找“下一个排列”，也就是要找到增长最小的排列。

因此我们应该从尽可能从靠右侧（末尾）的位置开始增长。想象我们从末尾开始遍历数组，会遇到第一个波峰，也就是nums[i] > nums[i-1]（如果找不到，说明没有下一个排列，那么就把整个序列升序排列即可），而其右边的序列如果存在，一定是降序，否则当前就不是第一个波峰了；所以我们想要让原序列增大，在nums[i]右边为降序的情况下，我们只能去增大nums[i-1]，而我们又要最小程度地增大，因此我们就选择[i,len-1]下标范围里大于nums[i-1]中最小的那个数与nums[i-1]交换，而因为[i,len-1]为降序，因此我们从数组末尾查找，找到第一个大于nums[i-1]的值，就是需要交换的值；交换之后，因为i-1位置的数值已经比原来大了，所以一定满足大于原序列的条件，而为了满足是下一个排列，我们还需要把[i,len-1]位置的元素升序排列，至此就找到了“下一个排列”。

因此主要过程分为三部分：

1、从末尾寻找第一个nums[i] > nums[i-1]的位置，找不到就把整个数组升序排列并return。

2、从末尾寻找第一个大于nums[i-1]的值，和nums[i-1]交换。

3、将[i,len-1]位置升序排列。

代码：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
       int len=nums.size();
       int flag=0,i=0;
        for(i=len-1;i>0;i--){
            if(nums[i]>nums[i-1]){
                flag=1;
                break;
            }
        }
        if(flag==0){
           sort(nums.begin(),nums.end());
             return;
        }

        for(int j=len-1;j>i-1;j--){
            if(nums[j]>nums[i-1]){
                swap(nums[j], nums[i-1]);
                break;
            }
        }
        sort(nums.begin()+i,nums.end());
        return ;
    }
};

要点：

之前很少使用sort函数，sort(nums[i], nums[j])的方法是错误的，而应该写作sort(nums.begin()+i,nums.end())。