“This is the 10th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Total number of orders in leetcode-1801 backlog

Subject to introduce

The original topic is quite long, and the description is also difficult to understand. I will make an introduction to the topic in plain English (please click the link above to see the original topic).

  1. And they’re going to pass in a two-dimensional array, which looks like this[[price1, amount1, orderType1], [price2, amount2, orderType2] ... ]
  • price: indicates the price of an order
  • orderType: Indicates the order type (0: purchase order, 1: sales order)
  • amount: indicates the number of orders of the same price and type
  1. The title rules
  • If a batch order is a purchase order, seeSelling backlogsExists inPrice less than or equal to purchase order priceIf the order exists, delete itThe purchase orderorSales backlog orders that are less than or equal to the purchase order price 的 Smaller values, the extra order quantity of the purchase order is added toPurchase backlog 中
  • If a batch order is a sales order, seePurchase backlogExists inThe price is greater than or equal to the sales order priceIf the order exists, delete itSales orderorPurchase an order from a backlog that is greater than or equal to the price of the sales order 的 Smaller values, the extra orders of sales orders are added toSelling backlogs 中
  • The last returnSelling backlogs 和 Purchase backlogThe total number of orders is right10 ^ 9 + 7The result of mod

Example 1

Example 2

Their thinking

The key to this question is to understand the rule of offsetting between orders. Purchase orders are compared from the lowest value in the sales backlog, so a small top heap can be used to maintain the sales backlog; The sales order is compared from the maximum in the purchase order, so a large top heap is used to maintain the purchase backlog

In this case, the total number of orders may be too large to put every order on the heap, which would cause memory overflow. The best approach is to store {price: ‘order price ‘, amount:’ order quantity ‘}, cancel out a certain number of orders on the top of the heap at a time, and then re-insert the remaining backlogs into the heap

The problem solving steps

  1. Create a big top heapbuystorePurchase backlogCreate a small top heapsellstoreSelling backlogs, the variabletotalSave the current backlog order total in real time
  2. Traversing the order list:
  • View if the current order is a purchase orderSelling backlogsIs there any order in
    • If not, place the current batch of purchase orders{price: 'order price ', amount:' order quantity '}insertBuy backorder buy,totalPlus the quantity of this purchase order
    • If yes, ejectThe backorder has been soldThe heap top element of
      • If heap top order quantityIs greater thanNumber of purchase orders, subtract the number of purchase orders from the number of heap top orders, and reinsert toThe backorder has been sold,totalSubtract the quantity of this purchase order
      • If heap top order quantityLess thanThe number of purchase orders, subtract the number of purchase orders from the number of heap top orders,totalSubtract the number of heap top orders and continue popping upThe backorder has been soldCompare the heap top elements with the remaining number of purchase orders and repeat the above steps
      • Finally, if the purchase order has a surplus, insert the remaining purchase order price and quantity intoBuy backorder buy 中
  • If the current order is a sales order, lookPurchase backlogIs there any order in
    • If not, the current batch of sales orders will be{price: 'order price ', amount:' order quantity '}insertThe backorder has been sold,totalPlus the quantity of this sales order
    • If yes, ejectBuy backorder buyThe heap top element of
      • If heap top order quantityIs greater thanThe number of sales orders, subtract the number of sales orders from the number of heap top orders, and reinsert toBuy backorder buy,totalSubtract the quantity of this sales order
      • If heap top order quantityLess thanThe number of sales orders, subtract the number of sales orders from the number of heap top orders,totalSubtract the number of heap top orders and continue popping upBuy backorder buyCompare the heap top elements with the remaining number of sales orders and repeat the above steps
      • Finally, if the sales order has a surplus, insert the remaining sales order price and quantity intoThe backorder has been sold 中
  1. Returns the resultTotal % (math.pow (10, 9) + 7)

The problem solving code

var getNumberOfBacklogOrders = function(orders) {
    // Buy backlogs
    const buy = new Heap(1)
    // Sell backlogs
    const sell = new Heap(-1)
    // Total backlog of orders
    let total = 0
    for (let [price, amount, orderType] of orders) {
        if (orderType === 0) { / / purchase
            // If the sales backlog is not empty && the heap top price is less than or equal to the purchase order price && The purchase order quantity is greater than 0
            while (sell.size() && sell.top().price <= price && amount > 0) {
                const head = sell.pop()
                if (amount < head.amount) { // If the purchase order quantity is smaller than the heap top order quantity
                    // Insert the extra heap top order number back into the sales backlog
                    sell.push({price: head.price, amount: head.amount - amount})
                    // The total backlog is less than offset by purchase orders
                    total -= amount
                    // Set the purchase order quantity to 0
                    amount = 0
                } else { // The number of purchase orders is greater than or equal to the number of heap top orders
                    // The purchase order quantity is less offset by the heap top order
                    amount -= head.amount
                    // The total backlog is less than offset by purchase orders
                    total -= head.amount
                }
            }
            // If the purchase order has a surplus, insert the remaining purchase order into the purchase backlog
            if (amount > 0) {
                buy.push({price, amount})
                total += amount
            }
        } else { / / sales
            // If the purchase backlog is not empty && the price of the heap top is greater than or equal to the price of the sales order && the number of sales orders is greater than 0
            while (buy.size() && buy.top().price >= price && amount > 0) {
                const head = buy.pop()
                if (amount < head.amount) { // If the sales order quantity is smaller than the heap top order quantity
                    // Insert the extra heap top order quantity back into the purchase backlog
                    buy.push({price: head.price, amount: head.amount - amount})
                    // The total backlog is less than offset by sales orders
                    total -= amount
                    // Set the number of sales orders to 0
                    amount = 0
                } else { // The number of sales orders is greater than or equal to the number of heap top orders
                    // The number of sales orders is less offset by heap top orders
                    amount -= head.amount
                    // The total backlog is less than offset by sales orders
                    total -= head.amount
                }
            }
            // If the sales order is left, insert the remaining sales order into the sales backlog
            if (amount > 0) {
                sell.push({price, amount})
                total += amount
            }
        }
    }
    return total % (Math.pow(10.9) + 7)};/ / class
class Heap {
    constructor(type) {
        this.arr = []
        // Generate a small top heap according to the value of type: -1 small top heap 1 big top heap
        this.type = type
    }

    // Return the heap size
    size() {
        return this.arr.length
    }

    // Return the top of the heap element
    top() {
        return this.arr[0]}// Insert elements into the heap
    push(val) {
        this.arr.push(val)
        this._sortBack()
    }

    // Pop up the top of the heap element
    pop() {
        const val = this.arr[0]
        const back = this.arr.pop()
        if (this.size()) {
            this.arr[0] = back
            this._sortFront()
        }
        return val
    }

    // Adjust the heap structure upward
    _sortBack() {
        let i = this.size() - 1
        if (this.type === -1) {
            while (i > 0 && this.arr[i].price < this.arr[Math.floor((i - 1) / 2)].price) {
                [this.arr[i], this.arr[Math.floor((i - 1) / 2)]] = [this.arr[Math.floor((i - 1) / 2)].this.arr[i]]
                i = Math.floor((i - 1) / 2)}}else {
            while (i > 0 && this.arr[i].price > this.arr[Math.floor((i - 1) / 2)].price) {
                [this.arr[i], this.arr[Math.floor((i - 1) / 2)]] = [this.arr[Math.floor((i - 1) / 2)].this.arr[i]]
                i = Math.floor((i - 1) / 2)}}}// Adjust the heap structure downward
    _sortFront() {
        let i = 0
        if (this.type === -1) {
            while (i * 2 + 1 < this.size()) {
                let temp = i
                if (this.arr[temp].price > this.arr[i * 2 + 1].price) temp = i * 2 + 1
                if (i * 2 + 2 < this.size() && this.arr[temp].price > this.arr[i * 2 + 2].price) temp = i * 2 + 2
                if (temp === i) break
                [this.arr[temp], this.arr[i]] = [this.arr[i], this.arr[temp]]
                i = temp
            }
        } else {
            while (i * 2 + 1 < this.size()) {
                let temp = i
                if (this.arr[temp].price < this.arr[i * 2 + 1].price) temp = i * 2 + 1
                if (i * 2 + 2 < this.size() && this.arr[temp].price < this.arr[i * 2 + 2].price) temp = i * 2 + 2
                if (temp === i) break
                [this.arr[temp], this.arr[i]] = [this.arr[i], this.arr[temp]]
                i = temp
            }
        }
    }
}
Copy the code