题目陈述

大意：定义波浪形序列为：序列中间的每个数都大于他的相邻的数或者小于他相邻的数。大小定义为字典序大小，求长度为n的序列中第k个波浪型的序列。

算法一：朴素算法

算法思路

• 一个很显然的思路，就是暴力枚举，字典序递增算出每一个序列，直到第k个

• 开一个vector来记录当前的序列，第i层代表当前要填写的是第i个数字，那么递归边界就是n+1层（前面n个数字都已经填写完毕）

• 那么我们该如何按字典序搜索？对于同一个位置填写的i，下一个位置如果填写的下降的，显然比上升的字典序来的小，所以应该先搜索下降的，再搜索上升的

• 如果确定了前两个数的关系，整个序列的山顶和山谷的位置也就确定了，只需要定义一个f_inc不断在0,1翻转就行了

  代码实现

  typedef long long ll;
  typedef vector<int> vci;
  #define pb push_back
  const int N = 22;
  class Solution
  {
  public:
    bool vis[N], findAns;
    vci ans;
    ll num;
    void dfs(int now, int last, bool f_inc, int &n, ll &k)
    {
        if (now == n + 1)//获得一个合法的序列
        {
            num++;
            if (num == k)//需找到答案
            {
                findAns = 1;
                return;
            }
            return;
        }
        if (!f_inc)
        { //当前位置是山顶
            for (int i = last + 1; i <= n; i++)
            {
                if (!vis[i])//如果i未使用
                {
                    ans.pb(i);//记录
                    vis[i] = 1;//标记已经使用
                    dfs(now + 1, i, f_inc ^ 1, n, k);//下一个位置跟当前位置的f_inc相反
                    if (findAns)
                        return;
                    vis[i] = 0;
                    ans.pop_back();//删除i
                }
            }
        }
        else
        {
            for (int i = 1; i < last; i++)
            { //当前位置是山谷
                if (!vis[i])//i未被使用过
                {
                    ans.pb(i);//记录
                    vis[i] = 1;//标记已经使用
                    dfs(now + 1, i, f_inc ^ 1, n, k);//下一个位置跟当前位置的f_inc相反
                    if (findAns)
                        return;
                    vis[i] = 0;//还原
                    ans.pop_back();//删除I
                }
            }
        }
        return;
    }
    vci stick(int n, ll k)
    {
        ans.clear();
        num=0;
        findAns=0;
        memset(vis, 0, sizeof vis);
        for (int i = 1; i <= n; i++)
        {
            ans.push_back(i);//记录
            vis[i] = 1;
            dfs(2, i, 1, n, k); //第一个位置是山顶，下一个位置是山谷(f_inc==1)
            //因为对于同样一个i，下一个位置如果越小，则字典序更小
            //所以下一个位置优先是山谷，f_inc=1
            if (findAns)//如果找到答案则返回
            {
                return ans;
            }
  
            dfs(2, i, 0, n, k); //第一个位置是山谷，下一个位置是山顶(f_inc==0)
            //搜索下一个位置是山顶的情况，即f_inc=0
            if (findAns)
                return ans;
            vis[i] = 0;
            ans.pop_back();//将尾巴弹出
        }
        return {};//牛客编译器必须有返回值
    }
  };

  复杂度分析

• 时间复杂度，对于第一个位置上面都填写的i,综合开头上升和开头下降来看，比他小的所有数，和比他大的所有数，都会被枚举一遍，对于第j个位置类似，已经选取j个数字，剩下的n-j个数字都会在第j+1个位置枚举一遍，故时间复杂度为。

• 空间复杂度，定义了动态数组ans，和数组vis，为

  算法二：数位DP+set维护

  算法思路

• 显然上述算法还是会TLE的，所以我们仍然需要优化

• 做题的时候，如果我们想到了上述的暴力写法并且打了出来，那么我们可以根据已有的代码，打表找规律

• 约定：开头是递增的称为上升序列，否则称为下降序列

• 如果在长度为3的上升序列前面加上4，那么就得到了长度为4的下降序列。

• 我们不妨大胆猜测，长度为n-1的上升序列，是否存在着某种转换，可以变为长度为n的下降序列？

• 下面我们思路继续推进

  思路推进

  打表

• 我们可以打表（暴力或者自己写）得到以下的序列

• 长度为4的波浪形序列

  1 3 2 4 
  1 4 2 3 
  2 1 4 3 
  2 3 1 4
  2 4 1 3
  3 1 4 2
  3 2 4 1
  3 4 1 2
  4 1 3 2
  4 2 3 1

• 还有长度为5的

  1 3 2 5 4 
  1 4 2 5 3 
  1 4 3 5 2 
  1 5 2 4 3 
  1 5 3 4 2 
  2 1 4 3 5
  2 1 5 3 4
  2 3 1 5 4
  2 4 1 5 3
  2 4 3 5 1
  2 5 1 4 3
  2 5 3 4 1
  3 1 4 2 5
  3 1 5 2 4
  3 2 4 1 5
  3 2 5 1 4
  3 4 1 5 2
  3 4 2 5 1 
  3 5 1 4 2
  3 5 2 4 1
  4 1 3 2 5
  4 1 5 2 3
  4 2 3 1 5
  4 2 5 1 3
  4 3 5 1 2
  4 5 1 3 2
  4 5 2 3 1
  5 1 3 2 4
  5 1 4 2 3
  5 2 3 1 4
  5 2 4 1 3

  序列的变换——状态转移方程

• 约定：**代表长度为以开头的波浪形序列，为上升序列，为下降序列**

• 此处我先给出下降序列的状态转移方程

  

• 再看我的解释，应该就更好理解如何变换到，其中

• 我们假如在前面加上一个2，如
  {1,3,2,4}-->{2,1,3,2,4}那么他是不是一个长度为5的序列？

• 当然我们还得把原本的那个2给换成5，就变成了{2,1,3,5,4}，肯定有读者想问显然这依旧不是一个波浪形序列？

• 对的，所以还需要再变换{2,1,3,5,4}-->{2,1,5,3,4}将5和3、4中小的那个交换,这样就得到了一个下降序列

• 肯定有同学想问，为什么要跟小的那个交换，就不能直接换成{n,最小,次小}的格式吗，我们看下面的例子

  {1,3,2,4}-->{2,1,5,3,4}
  {1,4,2,3}-->{2,1,4,3,5}

• 如果我们按照上述的同学的方法来做的话，显然第二个序列和第一个序列就会映射到同一个，就不符合1对1的映射

• 接下来我们来总结一下变换的步骤

1. 将i放在最前面
2. 将原本的i改为n
3. 因为n必然是最大的数，所以要使他变为山峰，将n跟他左右中较小的数交换
4. （如果n在最右边就跟左边那个数交换）

• 故所以对于所有的数，都可以从变换到，即状态转移方程为

  上升序列的DP方程

• 此处依旧先给出dp方程
• 理解了下降序列的状态转移方程，现在理解上升序列的状态转移方程应该容易一些
• 下面我们分裂讨论j的情况

  对于j==i的变换方式

  2 1 4 3-->2 5 1 4 3，对于P(n-1,i,0)，只需要在i后面添加上n，因为n必然是最大的，所以也就变成了上升序列

  对于j>i，且i的原位置是山顶

• 我们在j前面加上i，{3,4,1,2}-->{2,3,4,1,2}
• 再把原本的2换成5，因为2原本就是山顶，故换完之后无需变换,{2,3,4,1,2}-->{2,3,4,1,5}

  对于j>i，且i的原位置是山谷

• 因为n比所有数都要打，故换完之后需要调整
• 调整方式跟下降序列的调整方式一样
• {3,2,4,1}-->{2,3,2,4,1}-->{2,3,5,4,1}-->{2,5,3,4,1}

故每一个都可以变换为唯一一个，其中，即状态转移方程为

再次推进

• 现在我们已经得知dp方程如下：

  

• 接下来我们就是利用dp方程来求解答案了，因为是字典序递增的，且第k个序列必然存在，所以我们可以遍历找到第个字典序开头的数字是哪一个

• 接下来我们要寻找的长度减少了1，我们也知道n-1对应的dp方程，但是已经使用过一个数了，里面的数不一定是1-n怎么办？

• 我们可以理解成一种哈希映射，将他们排个序，依次映射到1-n，序列的个数依旧不变

• 既能排序又能记录去掉的数，显然这个容器，set无疑

  动画演示

  

  代码实现

  C++

  typedef long long ll;
  typedef vector<int> vci;
  const int N=22;
  class Solution {
    public:
        ll dp[N][N][2];
        //归类一下，序列可以分为有两种
        //dp[n][k][0,1]代表序列长度为n位
        ，首位是k，
        //先下降(0表示)或先上升(1表示)的序列数量
        ll decSum[N],incSum[N];
        vci stick(int n, ll k) {
            incSum[0]=0;
            dp[1][1][0]=dp[1][1][1]=1;
            //因为要考虑长度为len时，
            //对于len-1很多状态会改变，很多地方可以加入新的数len
            //所以借助辅助数组inc,incSum
            for(int len=2; len<=n; len++) {
                decSum[len]=0;
                for(int i=1; i<len; i++) {
                    incSum[i]=incSum[i-1]+dp[len-1][i][1];
                    //incSum代表长度为len-1的序列中，开头为1~i的上升序列的数量的前缀和
                }
                for(int i=len-1; i>=0; i--) {
                    decSum[i]=decSum[i+1]+dp[len-1][i][0];
                    //decSum代表长度为len-1的序列中，开头为i~len-1的下降序列的数量的后缀和
                }
                for(int i=1; i<=len; i++) {
                    dp[len][i][0]=incSum[i-1];//下降序列的数量，等于1~i-1的前缀和
                    dp[len][i][1]=decSum[i];//上升序列的数量，等于k~len-1对的后缀和
  
                }
            }
            int last;//记录上一个位置填写的是set中第几小的数字
            set<int> s;//记录哪些数字被用过了
            vci ans;//储存答案
            for(int i=1; i<=n; i++)s.insert(i);
            bool f_inc;
            for(int i=1; i<=n; i++) {
                //此处应该先比较下降序列的，再比较上升序列的
                //顺序不能调换，字典序原因
                if(dp[n][i][0]<k) { //说明还不在范围内，此处我们也可以用一个sum累加然后和k比较
                    k-=dp[n][i][0];//继续缩小范围
                } else {
                    last=i;
                    ans.push_back(i);//放入答案中
                    f_inc=1;//下一个位置是山顶
                    s.erase(i);//从维护的set中删除i,表示已经被用过了
                    break;
                }
                if(dp[n][i][1]<k) {
                    k-=dp[n][i][1];
                } else {
                    last=i;
                    ans.push_back(i);//放入答案中
                    f_inc=0;//下一个位置是山谷
                    s.erase(i);//从维护的set中删除i,表示已经被用过了
                    break;
                }
            }
            int idx;
            //上升代表当前位置是山谷，下降代表当前位置是山顶
            //长度逐渐减小的时候，dp数组中代表的1-n就可以理解成为离散化后的结果
            //可以理解成为哈希映射后的结果
            for(int len=n-1;len>=1;len--){
                if(f_inc)idx=1;//如果当前位置是山谷，则从1开始枚举
                //实际枚举区间为[1,last]，但是因为必然存在，故i到达len之前就已经break
                else idx=last;//如果当前位置是山顶，则从last开始枚举
                //实际枚举区间为[last,len]
                //之前的last已经被删除了
                for(int j=idx;j<=len;j++){
                    if(dp[len][j][f_inc]<k)k-=dp[len][j][f_inc];//继续缩小范围，分而治之
                    else {
                        auto it=s.begin();
                        for(int q=1;q<j;q++)it++;//因为迭代器不能直接+(j-1),故找set中第j小的数字得一步一步找
                        last=j;//对于下次来说，上次找的是第j小的数
                        ans.push_back(*it);
                        s.erase(it);
                        break;
                    }
                }
                f_inc^=1;//下一个位置，跟当前位置相反
            }
            return ans;
        }
  };

  python

  class Solution:
    def stick(self, n, k):
        inc = []
        ans = []
        now = 0
        dec =[[0 for i in range(n + 1)] for j in range(n + 1)]#python不能用连环等号
        #如果此处用连续等号，后面的dp数组会有问题
        inc = [[0 for i in range(n + 1)] for j in range(n + 1)]  # n+1个n+1个0，二维数组
        inc[1][1] = 1
        dec[1][1] = 1  # 初始长度为1
        vis = [0 for i in range(n + 1)]
        for Len in range(2, n + 1):  # 长度从2到n
  
            for i in range(1, Len + 1):  # 开头的数字从1到Len
                for m in range(1, i):  # 下降由上升1-（i-1）的和转移过来
                    dec[Len][i] += inc[Len - 1][m]
                for m in range(i, Len):  # 上升由下降i-(Len-1)的和转移过来
                    inc[Len][i] += dec[Len - 1][m]
        for i in range(1, n + 1):  # i从1到n，当前需要枚举的位置
            m = 0
            now = 0
            Len =n-i+1#剩余需要枚举的长度
            for j in range(1, n + 1):
                if (not vis[j]):  # 没有访问过
                    m += 1#相当于C++中的set来储存
                    #第i层计算ans中的第i个数，下标为ans[i-1]
                    if i == 1:
                        now = inc[Len][m] + dec[Len][m]
                    elif (j > ans[i - 2] and (i == 2 or ans[i - 2] < ans[i - 3])):#当前位置是山顶，即开头递减
                        now=dec[Len][m]
                    elif (j<ans[i-2] and (i==2 or ans[i-2]>ans[i-3])):#当前位置是山谷，即开头是递增
                        now=inc[Len][m]
  
                    if k<=now:
                        vis[j]=1#这个数被使用过了
                        ans.append(j)#放入答案
                        break
                    else:
                        k-=now
        return ans

  复杂度分析

• 时间复杂度，求解dp数组为,求解答案序列的第i个数字为,总共有n个数字，求解答案序列总得为，故整个算法的时间复杂度为。

• 空间复杂度，定义了上升和、下降和为，定义了答案序列为，定义了dp数组为，总得为