LeetCode - 1172 餐盘栈 （设计 - List + 小顶堆 + 栈））

List + 小顶堆 + 栈（双端队列实现的栈）

import java.util.*;

class DinnerPlates {
    
    //list 栈 双端队列
    //存放所有未满栈的下标的队列
    private PriorityQueue<Integer> deque;
    //按顺序存放所有栈
    private List<Deque<Integer>> list;
    //栈容量
    private int capacity;
    public DinnerPlates(int capacity) {
    
        this.capacity = capacity;
        //下标从小到大排序
        deque = new PriorityQueue<Integer>(new Comparator<Integer>(){
    
            public int compare(Integer i1,Integer i2){
    
                return i1.compareTo(i2);
            }
        });
        list= new ArrayList<>();
    }

    public void push(int val) {
    
        //如果当前存在没有满的栈
         if(deque.size() > 0){
    
             //取出从左至右第一个没有满的栈
             Deque<Integer> stack = list.get(deque.peek());
             //把val放入栈中
             stack.offerFirst(val);
             //如果栈满了
             //将该栈从未满栈队列中弹出
             if(stack.size() == this.capacity)
                  deque.poll();
         }
         else{
    //当前栈都满了
             //重新开一个栈
             Deque<Integer> stack = new LinkedList<>();
             //把val放入栈中
             stack.offerFirst(val);
             //将该栈放入栈队列中
             list.add(stack);
             //如果该栈没有满
             if(stack.size() < this.capacity){
    
                 //将栈加入未满栈队列中
                 deque.offer(list.size()-1);
             }
         }

    }

    public int pop() {
    
        //如果没有栈
        if(list.size() == 0)
             return -1;
        int val = -1;
        int index = list.size()-1;
        //将list末尾的空栈删除
        while(index >= 0 && list.get(index).size() == 0){
    
            list.remove(index);
            if(deque.contains(index))
                 deque.remove(index);
            index -= 1;
        }
        if(index >= 0 && list.get(index).size() > 0) {
    
             val = list.get(index).pollFirst();
            if(!deque.contains(index))
                deque.offer(index);
        }
        return val;
    }

    public int popAtStack(int index){
    
        if(index > list.size() -1)
            return -1;
        if(list.get(index).size() == 0)
            return -1;
        int val = list.get(index).pollFirst();
        if(!deque.contains(index))
            deque.offer(index);
        return val;
    }
}

/** * Your DinnerPlates object will be instantiated and called as such: * DinnerPlates obj = new DinnerPlates(capacity); * obj.push(val); * int param_2 = obj.pop(); * int param_3 = obj.popAtStack(index); */