31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

---

本题要求一个序列的下一个更大的序列，比如1,2,3 → 1,3,2，如果一个序列是最大的序列，如3,2,1，则返回其最小序列1,2,3。 算法从后往前扫描序列，如果从后往前看一直是上升的，如3,2,1，则说明这是最大的序列，直接将其逆序即可。 否则直到找到一个下降的转折点，比如4876543，找到48是下降的，这样我们就可以把4换成更大的数，但又不能太大，Next Permutation必须是紧跟在原序列后面的一个序列，所以我们从4的后面找比4大的最小的数，这里就是5。然后交换4和5，得到5876443，此时5后面仍然是有序的，而且是最大的，所以还要把5后面的序列逆序一下，得到5344678。 完整代码如下：

class Solution {
public:
    void nextPermutation(vector<int>& nums)
    { // 4876543
        for (int i = nums.size() – 1; i > 0; i–) {
            if (nums[i] > nums[i – 1]) { // 8 > 4
                int min_idx = i, min_val = INT_MAX;
                for (int j = nums.size() – 1; j > i; j–) {
                    if (nums[j] > nums[i – 1] && nums[j] < min_val) { // 5 > 4
                        min_idx = j;
                        min_val = nums[j];
                    }
                }
                swap(nums[i – 1], nums[min_idx]); // 5876443
                reverse(nums.begin() + i, nums.end()); // 5344678
                return;
            }
        }
        reverse(nums.begin(), nums.end());
    }
};

本代码提交AC，用时12MS。

二刷。时隔三年再刷此题，还是不会啊。需要注意的是为什么交换5和4之后，5后面的数依然是有序的呢，因为找到的是5是大于4的最小的数，所以4放到5的位置之后，4肯定小于它前面的数。我们可以用反证法证明4也会大于等于它后面的数，如果4小于它后面的数的话，则后面的数又小于5，那么5就不是大于4的最小的数，产生矛盾。

另外，还需要考虑到可能存在多个5的情况，此时应该把最后面的5和开头的4互换，否则互换后后面那部分的数就不是降序的了，所以j的循环是从后往前的。