2021-03-23 Leetcode-1801

1801.积压订单中的订单总数

今天又超时了:(

思路：维护两个集合sell和buy。遍历订单，根据订单数据判断入，出，删，略。
方法1：使用ArrayList作为集合，需要编写函数找出价格最低的销售订单，价格最高的采购订单。因此需要不断的遍历sell和buy两个集合。
方法2：使用TreeMap作为集合。根据文档。
TreeMap->NavigableMap->SortedMap->Map

The map is sorted according to the natural ordering of its keys
根据key值排序

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
操作的时间度为O(logn)。优于ArrayList遍历的O(n)。
同时TreeMap的firstKey(), lastKey()方法非常的方便

/*
执行用时：72 ms, 在所有 Java 提交中击败了15.89%的用户
内存消耗：86 MB, 在所有 Java 提交中击败了20.97%的用户
*/
public class Solution {
    public int getNumberOfBacklogOrders(int[][] orders) {
        TreeMap<Integer, Integer> sell = new TreeMap<>();
        TreeMap<Integer, Integer> buy = new TreeMap<>();

        for(int i=0; i < orders.length; i++){
            if(orders[i][2] == 0){
                int buyprice = orders[i][0];
                int buyamount = orders[i][1];
                if(sell.size() > 0){
                    //int minsellprice_i = findmaxminprice(sell)[0];
                    while(sell.size() > 0 &&  sell.firstKey() <= buyprice){
                        int minsellprice_i = sell.firstKey();
                        int left = sell.get(minsellprice_i) - buyamount;
                        if(left<= 0){
                            buyamount -= sell.get(minsellprice_i);
                            sell.remove(minsellprice_i);
                            if(buyamount == 0)  break;
                        }else{
                            sell.put(minsellprice_i,left);
                            buyamount=0;
                            break;
                        }
                    }
                }
                if(buyamount > 0){
                    buy.put(buyprice, buy.getOrDefault(buyprice, 0) + buyamount);
                }

            }
            if(orders[i][2] == 1){
                int sellprice = orders[i][0];                
                int sellamount = orders[i][1];
                if(buy.size() > 0){
                    //int maxbuyprice_i = findmaxminprice(buy)[1];
                    while(buy.size() > 0 && buy.lastKey() >= sellprice){
                        int maxbuyprice_i = buy.lastKey();
                        int left = buy.get(maxbuyprice_i) - sellamount;
                        if(left <= 0){
                            sellamount -= buy.get(maxbuyprice_i);
                            buy.remove(maxbuyprice_i);
                            if(sellamount == 0) break;
                        }else{
                            buy.put(maxbuyprice_i, left);
                            sellamount=0;
                            break;
                        }
                    }
                }
                if(sellamount > 0){
                    sell.put(sellprice, sell.getOrDefault(sellprice, 0) + sellamount);
                } 
                

            }
        }
        long amount = 0;
        for(Integer i : sell.values()){
            amount += i;
        }
        for(Integer i : buy.values()){
            amount += i; 
        }
        return (int)(amount % 1000000007);
    }
}