nextPermutation.cpp

#include <vector>
#include <algorithm>

using namespace std;

class Solution
{
public:
    void nextPermutation(vector<int> &nums)
    {
        //使用双指针来进行遍历数组
        int left = nums.size() - 2;
        int right = left + 1;
        bool ShouldBreak = false;

        //开始遍历，找到直到nums[i] < nums[i + 1]就停
        for(left;left >= 0;left--,right--)
        {
            if(nums[left] < nums[right])
            {
                //此时left记录的就是那个正好比右边那个数小的下标
                //再次遍历，直到nums[j] > nums[left]
                for(int j = nums.size() - 1;j >= 0;j--)
                {
                    if(nums[j] > nums[left])
                    {
                        //交换这两个位置上的数
                        int temp = nums[j];
                        nums[j] = nums[left];
                        nums[left] = temp;
                        ShouldBreak = true;
                        // 最终反转
                        reverse(nums.begin() + left + 1,nums.end()); 
                        break;
                    }
                }
            }
            if (ShouldBreak)
            {
                break;
            }
        }
        if(!ShouldBreak)
        {
            sort(nums.begin(),nums.end());
        }
    }
};