题解 | #牛牛摆木棒#

题目的主要信息：

• n根木棒，长度为1到n
• 对于要求的排列：第根木棒要求或者
• 求满足条件的排列中从小到大第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;
    }
};

复杂度分析：

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

方法二：动态规划

具体做法：
直接计算个数的排列组合，找到第k小实在是太复杂了，我们可以这样考虑：
我们设置动态规划的数组为表示共个数字且数字在首位的情况满足题目要求的波形数组共有多少种情况，其中第三维的0表示起始位置是升序，0表示起始位置是降序。

初始情况下，，只有1个数字，1必然为起点，升序降序都可以认为是1个，然后我们先枚举数组长度从1到n，再对于每种长度枚举每个数字在首位的情况，这样对于下一个长度一定来自于上一个长度的相反序情况数相加，于是我们有： 和，这样我们就可以得到，表示长度为的数组，以数字为起始的满足题目要求规则的排列的数量，因为相同起点情况下，升序一定比降序字典序要小，因此我们一般先检查升序即第三维为0的情况，且这里的第二维是从小到大的，也符合排列字典序的从小到大。因此我们遍历所有的找到第是在哪个的范围内，即找到首位数字且找到了首位是升序还是降序（因为先检查升序再检查降序）。
最后我们用集合记录1到n的所有数字，每次往答案中增加一个数字时，就从集合中删除它，防止重复添加。找到首位的数字后，我们不断缩短第一维（从n-1到1），按照每次找首位的方式不断向其中添加在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;
    }
};

复杂度分析：

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