2034. 股票价格波动

# 2034. 股票价格波动 (opens new window)

# 1.哈希+优先级队列

解题关键在于，在大根堆和小根堆中，如何处理被“更新覆盖”的最大值和最小值？

退一步思考，每次更新时有没有必要都修改大根堆和小根堆的元素？实际上，只需要在返回最大值和最小值时判断队列元素的价格是最新的还是旧的，而判断数据的新旧，只需要比对队列中的价格与当前最新价格是否一致即可。

核心是判断是否与最新价格相等来删除旧元素：

map哈希表key是时间戳timestamp，value是时间戳下最新的股票价格。
priorityQueue保存每次更新的时间戳，价格。

class StockPrice {
    int currPrice=0;
    int time=-1;
    Map<Integer,Integer> map;
    PriorityQueue<int[]> maxQueue;
    PriorityQueue<int[]> minQueue;
    public StockPrice() {
        maxQueue=new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                return o2[1]-o1[1];
            }
        });
        minQueue=new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                return o1[1]-o2[1];
            }
        });
        map=new HashMap<>();
    }
    public void update(int timestamp, int price) {
        if(timestamp>=time){
            time=timestamp;
            currPrice=price;
        }
        map.put(timestamp,price);
        maxQueue.offer(new int[]{timestamp,price});
        minQueue.offer(new int[]{timestamp,price});
    }
    public int current() {
        return currPrice;
    }
    
    public int maximum() {
        while(maxQueue.size()>0){
            int timestamp=maxQueue.peek()[0];
            int price=maxQueue.peek()[1];
            if(map.get(timestamp)!=price) maxQueue.poll();
            else return price;
        }
        return -1;
    }
    
    public int minimum() {
        while(minQueue.size()>0){
            int timestamp=minQueue.peek()[0];
            int price=minQueue.peek()[1];
            if(map.get(timestamp)!=price) minQueue.poll();
            else return price;
        }
        return -1;
    }
}