算法日常训练11.30（895.最大频率栈）

困难题，设计数据结构的，写的很少，直接看答案，发现看的懂，就直接看别人的答案学，这个答案是比较简单的，因为用了很多写好的数据结构，我们要做的就是对这些数据结构熟练掌握。

面向答案解释，优先队列用于实现栈的功能，自己自定义比较器，让他实现按频率弹出数据是比较简单的，但是如果有频率相同的数据，那么就要判断谁离栈顶更近，所以这里用index保存离栈顶的位置，还需要一个map来保存数据的次数，因为优先队列不能直接取出某一个数据来，那我们就不知道数据的次数，所以需要一个map保存，优先队列弹出以后map也要更新。

class FreqStack {
    private int index;//判定哪个离栈顶更近
    private Map<Integer,Integer> map;//保存数据出现的次数
    private PriorityQueue<int[]> queue;//模拟栈

    public FreqStack() {//初始化
        queue=new PriorityQueue<>(new Comparator<int[]>(){//自定义比较器
            public int compare(int[] o1,int[] o2){
                if(o1[1]==o2[1]){//出现次数相同，判断哪个离栈顶进
                    return o2[2]-o1[2];
                }
                return o2[1]-o1[1];//不然就是判断哪个是最大频率数字
            }
        });
        map=new HashMap<>();
        index=0;
    }
    
    public void push(int val) {
        int cnt=map.getOrDefault(val,0)+1;//次数
        map.put(val,cnt);
        queue.add(new int[]{val,cnt,index++});
    }
    
    public int pop() {
        int[] poll=queue.poll();
        map.put(poll[0],poll[1]-1);//更新次数
        return poll[0];
    }
}

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

差点就搞出来了，用的优先队列，但我想的是把通过率最低的班级排列，每次把最低的通过率的拿出来插一个学生进去，结果发现不能这样插，就以为自己优先队列这个想法是不通的，结果一看评论区发现一个几乎一样的答案，直接比增量就好了，不过也是踩着线过的，本来加了个输出数组的语句就超时了。

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
       PriorityQueue<int[]> queue=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                double avg1 = (o1[0] + 0.0) / o1[1];
                double avg2 = (o2[0] + 0.0) / o2[1];

                double avg1_add = (o1[0] + 1.0) / (o1[1] + 1.0);
                double avg2_add = (o2[0] + 1.0) / (o2[1] + 1.0);

                double res = Double.compare(avg1_add - avg1, avg2_add - avg2);
                if (res > 0) {
                    return -1;
                } else {
                    return 1;
                }
            }
        });
        Collections.addAll(queue,classes);
        while(extraStudents>0){
            int[] arr=queue.poll();
            queue.offer(new int[]{arr[0]+1,arr[1]+1});
            extraStudents--;
        }
        double res=0;
        while(!queue.isEmpty()){
            int[] arr=queue.poll();
            res+=((double)arr[0]/arr[1]);
        }
        return res/classes.length;

    }
}