题解 | #牛牛摆木棒#

题目的主要信息：

n根木棒，长度为1到n
对于要求的排列：第 $i$ 根 $(2<=i<=n-1)$ 木棒要求 $(a_i>a_{i-1} 且 a_i>a_{i+1})$ 或者 $(a_i<a_{i-1} 且 a_i<a_{i+1})$
求满足条件的排列中从小到大第k个排列

方法一：暴力枚举（超时）

具体做法：
我们首先构造一个从1到n的数组，这是这n个数排列的最小值，然后利用next_permutation函数依次构造其余的排列，它会从小到大构造。对于每个构造出来的排列，我们遍历数组检查是否满足上述要求，满足要求k减1直到k为0，返回这个排列。

class Solution {
public:
    bool check(vector<int>& a){
        for(int i = 1; i < a.size() - 1; i++){ //遍历数组，检验
            if((a[i] > a[i - 1] && a[i] > a[i + 1]) || (a[i] < a[i - 1] && a[i] < a[i + 1]))
                continue;
            else
                return false;
        }
        return true;
    }
    vector<int> stick(int n, long long k) {
        vector<int> res(n, 0);
        for(int i = 1; i <= n; i++) //构建最小排列
            res[i - 1] = i;
        do{
            if(check(res)) //检查该排列是否合法
                k--;
            if(k == 0)
                break;
        }while(next_permutation(res.begin(), res.end())); //生成下一个排列
        return res;
    }
};

复杂度分析：

时间复杂度： $(n*(n!))$ ，最坏情况需要将 $n$ 个数字全部全排列，然后每次检查遍历数组都是 $O(n)$
空间复杂度： $O(1)$ ，res数组属于返回函数必要空间，不属于额外空间

方法二：动态规划

具体做法：
直接计算 $n$ 个数的排列组合，找到第k小实在是太复杂了，我们可以这样考虑：
我们设置动态规划的数组为 $dp[i][j][0/1]$ 表示共 $i$ 个数字且数字 $j$ 在首位的情况满足题目要求的波形数组共有多少种情况，其中第三维的0表示起始位置是升序，0表示起始位置是降序。
图片说明
初始情况下， $dp[1][1][0] = dp[1][1][1] = 1$ ，只有1个数字，1必然为起点，升序降序都可以认为是1个，然后我们先枚举数组长度从1到n，再对于每种长度枚举每个数字在首位的情况，这样对于下一个长度一定来自于上一个长度的相反序情况数相加，于是我们有： $dp[i][j][0] = \Sigma_{k=1}^{j-1} dp[i-1][k][1]$ 和 $dp[i][j][1]=\Sigma_{k=j+1}^{n} dp[i-1][k-1][0]$ ，这样我们就可以得到 $dp[n][i][0/1]$ ，表示长度为 $n$ 的数组，以数字 $i$ 为起始的满足题目要求规则的排列的数量，因为相同起点情况下，升序一定比降序字典序要小，因此我们一般先检查升序即第三维为0的情况，且这里的第二维 $i$ 是从小到大的，也符合排列字典序的从小到大。因此我们遍历所有的 $i$ 找到第 $k$ 是在哪个 $i$ 的范围内，即找到首位数字且找到了首位是升序还是降序（因为先检查升序再检查降序）。
最后我们用集合记录1到n的所有数字，每次往答案中增加一个数字时，就从集合中删除它，防止重复添加。找到首位的数字后，我们不断缩短第一维（从n-1到1），按照每次找首位的方式不断向其中添加 $k$ 在dp数组显示的范围内的数字即可，需要注意的是交替升降序。添加到最后一个数字时，k刚好为0，即找到我们所需要的排列。

class Solution {
public:
    vector<int> stick(int n, long long k) {
        vector<vector<vector<long long> > > dp(n + 1, vector<vector<long long>>(n + 1, vector<long long>(2, 0)));
        vector<int> res;
        dp[1][1][0] = 1; //初始化
        dp[1][1][1] = 1;
        //构造n个长度数组，每个数字开头的先上（0）或者先下（1）波形数组的个数
        for(int i = 2; i <= n; i++){ //先枚举数组长度
            for(int j = 1; j <= i; j++){ //再枚举起点数字
                for(int m = 1; m < j; m++){ //先增序首木棒数字加上之前i-1根的种类数
                    dp[i][j][0] += dp[i - 1][m][1];
                }
                for(int m = j + 1; m <= i; m++){
                    dp[i][j][1] += dp[i - 1][m - 1][0]; //先减序首木棒数字加上之前i-1根的种类数
                }
            }
        }
        set<int> S; //保存没用过的数字
        int flag; //记录首位升序还是降序
        int cur; //记录答案数组中最后一位数字
        for(int i = 1; i <= n; i++) //1到n先全部进入集合
            S.insert(i);
        for(int i = 1; i <= n; i++){ //找到满足第k小的首数字
            if(dp[n][i][0] < k) //不如k大，用k减掉，直到遇到满足k在里面的首数字，升序小于降序，因此先判断首位升序
                k -= dp[n][i][0];
            else{
                res.push_back(i); //首位进入
                cur = i; //记录首位数字
                flag = 0;  //升序
                S.erase(i);  //移除该数字
                break;
            }
            if(dp[n][i][1] < k) //再判断首位降序
                k -= dp[n][i][1];
            else{
                res.push_back(i);
                cur = i;
                flag = 1;
                S.erase(i);
                break;
            }
        }
        int start;
        for(int i = n - 1; i >= 1; i--){ //补齐首位后面的
            flag = 1 - flag; //升降序交替
            if(flag) //降序从最小的开始
                start = 1;
            else //升序从当前新结尾开始
                start = cur;
            for(int j = start; j <= i; j++){
                if(dp[i][j][flag] < k) 
                    k -= dp[i][j][flag]; //k减去这里的次数
                else{
                    auto iter = S.begin();
                    for(int m = 1; m < j; m++)
                        iter++;
                    res.push_back(*iter); //加入新的元素
                    S.erase(iter); //删除这个数字
                    cur = j; //更新其起始
                    break;
                }
            }
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n^3)$ ，填充dp数组三次循环，为 $O(n^3)$ ，初始化set集合及找到首位元素都是单次循环，为 $O(n)$ ，后续补齐后面的元素双层循环，为 $O(n^2)$ ，去掉低次幂即可
空间复杂度： $O(n^2)$ ，最大空间为dp数组的空间