原题链接

力扣，下一个排列

给定一个数字排列，求出字典序下的下一个排列。

思路与解答

没有想出来

本题实际上就是让我们调整数字的顺序，恰好获得字典序下的下一个排列，听起来很简单，但是其中有挺多细节：

  1. 怎么正好生成下一个排列？
  2. 遇到升序、降序的corner case如何处理？

自己当时陷进了DFS的思维定式，没有想到直接从字典序本身考虑，说明我自身的算法思维还是存在一定的缺陷。

首先写几组数字观察一下：

1
2
3
4
5
6
7
8
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1 2 3
. . .

可以发现，字典序变大的过程实际上就是数组中逆序对变多的过程（不过感觉这个观察没有什么用啊岂可修），更具体地，一个任意区间的字典序最大为所有数字非增排列，如果想要继续增加，那么必然需要进位，也就是将该段数组中的一个元素与该区间外的一个小数字进行交换，然后将该区间之内的数字全部升序。

例如，1 3 2中，3 2是尾部的非增区间，此时无论尾部怎么调换，必然无法增加字典序，就需要将其中最小的一个数字与该区间左侧第一个元素进行交换，也就是2与1交换，得到2 3 1，不过这样一来并不是1 3 2的下一个排列，我们需要将原先的区间倒置，其此时必然变成一个升序排列，并且一定是原先排列的下一个排列。

我们再用一个特殊的例子看一下：3 2 1，由于尾部非增区间实际上就已经是整个数组，故而一定无法继续递增字典序，跳过了交换数字的过程，直接将整个区间逆转。

总结该算法：

  1. 找到尾部最长的非增序列，不是递减是因为可能存在相同的数字；
  2. 如果非增区间已经是整个数组，那么直接进入下一步；否则，在非增区间中找到最小的大于非增区间左侧第一个元素的值，交换他们（形象地说，就是进位）；
  3. 将非增区间逆转。

实际上，C++ STL中的next_permutation就是使用的这个算法。

实现

注意到非增区间具有有序性，故而查找可以使用二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int j = nums.size()-1;
        while(j && nums[j-1]>=nums[j]){// 找到分界点
            j--;
        }


        reverse(nums.begin()+j, nums.end());// 保持有序，否则无法进行二分查找

        if(j){
            int i = j-1;
            int ind = upper_bound(nums.begin()+j,nums.end(), nums[i])-nums.begin();
            if(ind!=nums.size())
                swap(nums[i], nums[ind]);
        }
    }
};