优先队列专题

Mr.He...

lc-855 Mid

todo

lc-1801 Mid

根据题意，创建2个优先队列，其比较规则相反。然后遍历orders。在循环中，先判断当前订单是否为采购类。

如果是，则继续判断（while）：如果销售订单队列不为空，且其第一个元素的价格小于当前订单的价格，且当前订单的数量大于0，则进入while循环。

循环内，先获取当前用户的数量和销售队列中第一个元素的数量的最小值，然后分别在数量上减去这个最小值。如果销售队列第一个元素的数量被减为0，则移除它。

循环结束后判断，如果当前元素数量还大于0，则把它加入到采购队列中。

外层orders的循环中，对销售类订单的循环和采购类类似。

循环结束后，需要分别获取两个优先队列中，每个订单的数量之和。使用Java8的Stream简化代码。最后再对1000000007L取余后，返回结果。

class Solution {
    Queue<int[]> buy = new PriorityQueue<>((a, b)-> b[0] - a[0]);
    Queue<int[]> sell = new PriorityQueue<>((a, b)-> a[0] - b[0]);

    public int getNumberOfBacklogOrders(int[][] orders) {
        for (int[] order : orders) {
            checkAndRemove(order);
        }
        return getSum();
    }

    private int getSum() {
        return (int)((buy.stream().mapToLong(arr -> arr[1]).sum() + sell.stream().mapToLong(arr -> arr[1]).sum()) %
                (1000000007L));
    }

    /**
     * 检查对应的队列中，是否有需要消除的元素。
     * @param cur
     */
    private void checkAndRemove(int[] cur) {
        if (cur[2] == 0) { // 当前是采购订单，查询销售订单列表。
            while (!sell.isEmpty() && sell.peek()[0] <= cur[0] && cur[1] > 0) {
                int min = Math.min(sell.peek()[1], cur[1]);
                cur[1] -= min;
                sell.peek()[1] -= min;
                if (sell.peek()[1] == 0) {
                    sell.remove();
                }
            }
            if (cur[1] > 0) {
                buy.add(cur);
            }
        } else {
            while (!buy.isEmpty() && buy.peek()[0] >= cur[0] && cur[1] > 0) {
                int min = Math.min(buy.peek()[1], cur[1]);
                cur[1] -= min;
                buy.peek()[1] -= min;
                if (buy.peek()[1] == 0) {
                    buy.remove();
                }
            }
            if (cur[1] > 0) {
                sell.add(cur);
            }
        }
    }
}