02、面试题 03.06. 动物收容所 https://leetcode-cn.com/problems/animal-shelter-lcci/
动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat。允许使用Java内置的LinkedList数据结构。
enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。
dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。

输入：
["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [], [], []]
输出：
[null,null,null,[0,0],[-1,-1],[1,0]]

class AnimalShelf {
   LinkedList<int[]> queueCat;
   LinkedList<int[]> queueDog;

   public AnimalShelf() {
       queueCat = new LinkedList<>();
       queueDog = new LinkedList<>();
   }

   public void enqueue(int[] animal) {
       // 判断种类后入队
       if (animal[1] == 0) {
           queueCat.addLast(animal);
       } else if (animal[1] == 1) {
           queueDog.addLast(animal);
       }
   }

   public int[] dequeueAny() {
       // 取出cat的队首，判空则直接返回
       int[] headCat;
       if (!queueCat.isEmpty()) {
           headCat = queueCat.getFirst();
       } else if (!queueDog.isEmpty()) {
           return queueDog.removeFirst();
       } else {
           return new int[]{-1,-1};
       }
       // 取出dog的队首，判空则直接返回
       int[] headDog;
       if (!queueDog.isEmpty()) {
           headDog = queueDog.getFirst();
       } else {
           return queueCat.removeFirst();
       }
       // 比较后返回
       if (headCat[0]<=headDog[0]) {
           return queueCat.removeFirst();
       } else {
           return queueDog.removeFirst();
       }
   }

   public int[] dequeueDog() {
       if (!queueDog.isEmpty()) {
           return queueDog.removeFirst();
       } else {
           return new int[]{-1,-1};
       }
   }

   public int[] dequeueCat() {
       if (!queueCat.isEmpty()) {
           return queueCat.removeFirst();
       } else {
           return new int[]{-1,-1};
       }
   }
}

01、42. 接雨水https://leetcode-cn.com/problems/trapping-rain-water/
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        if (height==null || height.length == 0){
            return sum;
        }
        Stack<Integer> stack = new Stack();
        for (int i = 0; i < height.length; i++) {
            while (!stack.empty() && height[i] > height[stack.peek()] ){
                int h = height[stack.peek()];
                stack.pop();
                if (stack.empty()){
                    break;
                }
                int distance = i - stack.peek() -1;
                int min = Math.min(height[i],height[stack.peek()]);
                sum += distance * (min - h);
            }
            stack.push(i);
        }
        return sum;
    }
}