算法分析

(递归)

• 1、直接上y总的视频中的某一个时刻截图

• 2、维护好3个状态

  • state1表示出栈元素排队的状态，使用链表list维护

  • state2表示当前栈元素的状态，使用栈stack维护

  • state3表示当前第几个元素准备进栈，使用整数int维护

• 3、整个系统有两个操作情况
  一：将整数state3的元素进入到state2栈中
  二：将栈state2的元素出栈到state3链表中

• 4、由于题目要求按《字典序》输出前20种可能的出栈方案，所以需要优先执行二操作

注意：该2的20次方是操作次数的上界（为下一题130题做铺垫）

参考文献

参考y总的视频讲解

Java 代码

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.Scanner;
public class Main {
    //维护好3个状态
    static List<Integer> state1 = new ArrayList<Integer>();
    static Stack<Integer> state2 = new Stack<Integer>();
    static int state3 = 1;
    static int cnt = 20;//执行20层
    static int n;
    public static void dfs()
    {
        if(cnt == 0) return;
        //符号条件执行打印操作
        if(state1.size() == n)
        {
            cnt --;
            for(Integer i : state1) System.out.print(i);
            System.out.println();
            return;
        }
        //执行2操作
        if(!state2.isEmpty())
        {
            state1.add(state2.pop());
            dfs();
            //回复现场
            state2.push(state1.remove(state1.size() - 1));
        }
        //执行1操作
        if(state3 <= n)
        {
            state2.push(state3);
            state3 ++;
            dfs();
            //恢复现场
            state3 --;
            state2.pop();
        }
        //执行1操作
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        dfs();
    }
}