出栈的合法顺序

(这是一篇水贴)

在把1到n这n个数依次入栈的情况下,如何判断出栈的顺序是否合法?

如果仅仅要求顺序合法,我们可以在已经得到了一个出栈序列的情况下,以如下的方式判断。

         int A=1,B=1;
         stack s;
         while(A<=n){
             if(a[A]==B){
                 A++;B++;
             }
             else if(!s.empty()&&s.top()==a[A]){
                 s.pop();
                 A++;
             }
             else if(B<=n){
                 s.push(B++);
             }
             else {
                 break;//不合法
             }
         }

我们可以以生成全排列的方法,借用这种判断方式来暴力求出合理的出栈顺序的数量。(当然,可以数论直接求解)

也可以直接高效生成(以下代码来自SE大佬):

      inline void dfs(int s) {
      if(cnt == n) {
      num++;
      /* 
      for (int i = 1;i <= n; ++i) printf("%d", c[i]);  
      printf("\n");  
      */  
      return;  
  }
  if (top > 0) {
      int tp = a[top--];  
      c[++cnt] = tp;  
      dfs(s);  
      a[++top] = tp;
      cnt--;   
  }
  if (s <= n) { 
      a[++top] = s;  
      dfs(s+1);  
      top--;  
   }  
 }  
  int main(){  
      scanf("%d", &n);  
      dfs(1); 
      printf("%d", num);  
      return 0;  
  }  

留下评论

您的电子邮箱地址不会被公开。