本文共 2581 字，大约阅读时间需要 8 分钟。

[编程题]: 入栈出栈序列

题目描述

输入n，入栈序列为[1, 2, …, n]

结题思路

给定包含n个数的入栈序列，出栈序列的可能情况根据卡特兰公式有

示例

n = 4那么入栈序列为 [1, 2, 3, 4]可能的出栈序列为:[1, 2, 3, 4],[1, 2, 4, 3],[1, 3, 2, 4],[1, 3, 4, 2],[1, 4, 3, 2],[2, 1, 3, 4],[2, 1, 4, 3],[2, 3, 1, 4],[2, 3, 4, 1],[2, 4, 3, 1],[3, 2, 1, 4],[3, 2, 4, 1],[3, 4, 2, 1],[4, 3, 2, 1]

共14种。

代码

package demo;import java.util.ArrayList;import java.util.List;import java.util.Scanner;import java.util.Stack;public class Main {
       private static List
   
    
     > res = new ArrayList<>();    public static void main(String[] args) {
           Scanner input = new Scanner(System.in);        int T = input.nextInt();        for (int times = 0; times < T; times++) {
               int n = input.nextInt();            res.clear();            helper(n, 1, new ArrayList<>(), new boolean[n + 1]);            int line = 0;            for (int i = 0; i < res.size(); i++) {
                   System.out.print(res.get(i));                line++;                if (line < 3 && i < res.size() - 1) System.out.print(",");                else {
                       System.out.println();                    line = 0;                }            }        }    }    private static void helper(int n, int index, List
     
       nums, boolean[] visited) {
           if (index == n + 1) {
               boolean ans = check(n, nums);            if (ans) res.add(new ArrayList<>(nums));            return;        } else {
               for (int i = 1; i <= n; i++) {
                   if (visited[i]) continue;                visited[i] = true;                nums.add(i);                helper(n, index + 1, nums, visited);                nums.remove(nums.size() - 1);                visited[i] = false;            }        }    }    private static boolean check(int n, List
      
        nums) {
           int num1 = 1;        int index2 = 0;        Stack
       
         stack = new Stack<>();        while (num1 <= n || index2 < n) {
               if (num1 == nums.get(index2)) {
                   num1++;                index2++;            }            else {
                   if (!stack.isEmpty() && stack.peek() == nums.get(index2)) {
                       stack.pop();                    index2++;                } else {
                       if (num1 > n) return false; // 入栈序列入完栈仍然不能找到相等的情况                    stack.push(num1);                    num1++;                }            }        }        if (stack.isEmpty() && num1 == n + 1 && index2 == n) return true;        else return false;    }}