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

考察知识点：数组、双指针

题目分析：

因为在字典序中如果一个序列是单调递增的，那么这个序列就是由这些数所组成的最小序列。我们要找到一个较小的序列，可以从后向前遍历，找到第一个左边比右边大的数。例如 1 2 3 4 7 6 5 8 9

然后6之后的数就一定是一个递增的序列。在这个序列中找到第一个比6小的数，就是5。为什么找比6小的数？我们可以看到如果我们取比6大的数来交换，那么新的序列就会比原序列大，所以我们应找在右边的递增序列中到比6小的最大的那个数（第一个比6小的数）。

交换这两个数的位置之后发现仍然不满足条件，因为此时6 8 9 是递增序列，是之前的所有数确定好后的最小序列。而由于5和6的交换一定使序列变小了，我们应该考虑怎样确定6、8和9才能让这个较小值最大。让较小值最大就是找到比原序列在字典序中更小一个的排列。很明显应该将6、8 和9降序排列。由于6、8 和 9这部分一定是升序的，所以我们翻转这部分即可得到降序序列。

所用编程语言：Ｃ++

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