Daily LeetCode – day0157 1801. Number of Orders in the Backlog

import java.util.PriorityQueue;

// 1801. Number of Orders in the Backlog
class Solution {
    public int getNumberOfBacklogOrders(int[][] orders) {
        final long MOD = 1000000007L;
        PriorityQueue<Order> backlog0 = new PriorityQueue<>(((o1, o2) -> (o2.price - o1.price)));
        PriorityQueue<Order> backlog1 = new PriorityQueue<>(((o1, o2) -> (o1.price - o2.price)));
        for (int[] order : orders) {
            int price = order[0];
            int amount = order[1];
            if (order[2] == 0) {
                while (amount > 0 && !backlog1.isEmpty() && price >= backlog1.peek().price) {
                    if (amount >= backlog1.peek().amount) {
                        amount -= backlog1.poll().amount;
                    } else {
                        backlog1.peek().amount -= amount;
                        amount = 0;
                    }
                }
                if (amount > 0) {
                    backlog0.offer(new Order(price, amount));
                }
            } else {
                while (amount > 0 && !backlog0.isEmpty() && price <= backlog0.peek().price) {
                    if (amount >= backlog0.peek().amount) {
                        amount -= backlog0.poll().amount;
                    } else {
                        backlog0.peek().amount -= amount;
                        amount = 0;
                    }
                }
                if (amount > 0) {
                    backlog1.offer(new Order(price, amount));
                }
            }
        }
        long ans = 0L;
        while (!backlog0.isEmpty()) {
            ans = (ans + backlog0.poll().amount) % MOD;
        }
        while (!backlog1.isEmpty()) {
            ans = (ans + backlog1.poll().amount) % MOD;
        }
        return (int) ans;
    }
}

class Order {
    int price;
    int amount;

    public Order(int price, int amount) {
        this.price = price;
        this.amount = amount;
    }
}
学习笔记:
今天这道题目就是考察两个优先队列,分别是最大堆和最小堆。
描述了很多,做题的时候发现描述多写代码就按描述来就可以了。
有一种在做模拟算法的感觉。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注