题解 | #牛群的编号重排#

知识点

思维 双指针

思路

对一个排列，为获得比他小一个字典序的全排列，需要找一个较大的值，和右侧更小的一个值进行交换，这样才能让序列变小。

对于较大的值 i 来说，我们从后倒数第二个开始（给后面留一个数）往前找出第一个大于后方数字的值作为较大值 i。

然后在i的右方找出小于 i 的值，作为较小的值 j，将二者进行交换，交换完之后，i 位置右边的数需要重新排序，这样可以在保证新排列小于原来排列的情况下，使变小的幅度尽可能小。 例如132456，找到的cows[i]为3，cows[j]为2。交换后序列为123456，此时并非小一个的字典序，需要重新对[i+1,n-1]翻转，来维持字典序刚好小一个，得到126543，即为所求。

若这个排列已经是最小字典序的排列，那么i为0，翻转刚好将最小字典序变为了最大字典序。

代码

#include <iterator>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型vector 
     * @return int整型vector
     */
    vector<int> nextPermutation(vector<int>& cows) {
        // write code here
        int n=cows.size()-2;
        while(n>=0&&cows[n]<=cows[n+1])n--;
        int j=cows.size()-1;
        cout<<n<<endl;
        if(n>=0)
        {
            
            while(j>=0&&cows[n]<=cows[j])
            {
                j--;
            }
            cout<<j<<endl;
            swap(cows[n],cows[j]);
        }       
        reverse(cows.begin()+n+1,cows.end());
        return cows;
    }
};