【洛谷p1044】栈（全排列+栈的压入弹出序列）（卡特兰数）

待我称王封你为后i 2021-10-03 02:40 259阅读 0赞

## 题目背景 ##

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

## 题目描述 ##

![format_png][]

宁宁考虑的是这样一个问题：一个操作数序列，1,2,\\ldots ,n1,2,…,n（图示为 1 到 3 的情况），栈 A 的深度大于 nn。

现在可以进行两种操作，

1.  将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）
2.  将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 `1 2 3` 生成序列 `2 3 1` 的过程。

![format_png 1][]

（原始状态如上图所示）

你的程序将对给定的 nn，计算并输出由操作数序列 1,2,\\ldots,n1,2,…,n 经过操作可能得到的输出序列的总数。

## 输入格式 ##

输入文件只含一个整数 nn（1 \\leq n \\leq 181≤n≤18）。

## 输出格式 ##

输出文件只有一行，即可能输出序列的总数目。

我的做法：思路是对的，但是复杂度太高了。最后两个样例超时了。（希望有志之士帮我优化一下）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70][]

import java.util.*;
    public class Main{
        static void swap(int [] array,int i,int j){
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        static ArrayList<String> list = new ArrayList<>();
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int[] array = new int[n];
            for(int i = 0;i<array.length;i++){
                array[i] = i+1;
            }
            dfs(array,0,array.length-1);
            int count = 0;
            for(int i = 0;i<list.size();i++){
                if(isTrue(list.get(i),array)){
                    count++;
                };
            }
            System.out.println(count);
        }
    
        private static boolean isTrue(String s,int [] push) {
            char[] chars = s.toCharArray();
            Stack<Integer> stack = new Stack<>();
            int j = 0;
            for(int i = 0;i<push.length;i++){
                stack.push(push[i]);
                while (!stack.isEmpty() && (stack.peek() == Integer.valueOf(chars[j]-'0'))){
                    stack.pop();
                    j++;
                }
            }
            return stack.isEmpty();
        }
    
        private static void dfs(int[] array, int cur, int n) {
            if(cur == n){
                StringBuilder sb = new StringBuilder();
                for(int i = 0;i<array.length;i++){
                    sb.append(array[i]);
                }
                list.add(sb.toString());
                return;
            }
            for(int i = cur;i<=n;i++){
                swap(array,i,cur);
                dfs(array,cur+1,n);
                swap(array,i,cur);
            }
        }
    }

卡特兰数：

import java.util.*;
    public class Main{
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int [] array = new int[n+1];
            array[0] = 1;
            for(int i = 1;i<=n;i++){
                for(int j = 0;j<i;j++){
                    array[i]+=array[j]*array[i-j-1];
                }
            }
            System.out.println(array[n]);
        }
    }

[format_png]: /images/20211003/b134128bbf354e659d74c3ae40a9678e.png
[format_png 1]: /images/20211003/9b7cd4600ceb45c6b4485e683b338118.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70]: /images/20211003/6aa7a631594242e9ae683d6088ce718a.png