這道題本來想直接暴力回溯的，但是想了下還是算了，自己想這個思路完全想不出來，直接去看靈神的題解了，感覺還是很好懂的，強(qiáng)烈推薦去看看他的題解。
我們先討論最一般的情況：對于一組排列，我們要找到它的下一個排列，就需要從右往左遍歷，找到第一個小于右邊相鄰元素的位置。例如，對于排列[3, 5, 1, 4, 2, 6, 1]，我們要找下一個大于當(dāng)前數(shù)的排列(nums[i] < nums[i + 1])，我們就需要找到元素2的位置i，它是從右往左數(shù)，第一個小于右邊相鄰元素的數(shù)，此時我們還不能簡單地將2和6簡單交換位置就草草了事，因為如果輸入是[3, 5, 1, 4, 2, 6, 0]，將2和6交換位置將得到[3, 5, 1, 4, 6, 2, 0]，顯然，下一個排列應(yīng)當(dāng)為[3, 5, 1, 4, 6, 0, 2]。因此，在找到i之后，我們可以得到如下性質(zhì)：從i + 1到數(shù)組的最后一個元素，這段數(shù)字應(yīng)當(dāng)是降序排列的，這是因為i是從右往左數(shù)第一個小于右側(cè)相鄰元素的值，從i + 1到數(shù)組的倒數(shù)第二個元素，每一個元素都大于等于右邊相鄰的元素，從而形成降序排列。我們還需要尋找一個元素nums[j],使得nums[j]恰好為大于nums[i]的元素中的最小值，從右往左數(shù)，第一個大于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)這個區(qū)間是降序排列的，我們?nèi)孕枰獙ζ溥M(jìn)行逆轉(zhuǎn)為升序排列使其變得更小，最終得到下一個排列，因此我們通過reverse(nums.begin() + i + 1, nums.end());來實現(xiàn)反轉(zhuǎn)，從而得到下一個排列。
下面再來討論特殊情況，當(dāng)原排列已經(jīng)是最大的排列，不可能得到更大的排列時，我們需要將其轉(zhuǎn)化為最小的排列，最大的排列一定是從頭到尾都降序排列，我們將其逆轉(zhuǎn)，得到升序排列，此時一定是最小的排列。
綜上所述，如果我們能找到符合條件的i，那么我們還需要進(jìn)行第二步操作，找到符合條件的j，進(jìn)行交換，如果找不到，就直接執(zhí)行第三步操作。第三步，將指定范圍內(nèi)的排列逆序。最終得到下一個排列。

class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size();//1.從右往左尋找第一個小于右側(cè)相鄰元素的數(shù)int i = n - 2;while(i >= 0 && nums[i] >= nums[i + 1])i--;//2.如果找到了，那么一定滿足i >= 0,如果不滿足，則跳過第2步//此時從i + 1到末尾一定是單調(diào)遞減的，因為i是從右往左數(shù)第一個小于右側(cè)相鄰元素的值if(i >= 0){int j = n - 1;while(nums[j] <= nums[i])j--;swap(nums[i], nums[j]);   //交換i和j的位置，數(shù)值已經(jīng)變大，但是可能不是最接近原數(shù)的下一個排列}//3.如果存在對應(yīng)的i，則此階段需要進(jìn)行最后的微調(diào)，由于[i + 1, end)這個區(qū)間是降序排列的//我們?nèi)孕枰獙ζ溥M(jìn)行逆轉(zhuǎn)為升序排列使其變得更小//如果沒有找到合適的i，則說明原來的排列已經(jīng)是最大值，我們需要將其逆序排列得到最小值reverse(nums.begin() + i + 1, nums.end());}
};