751-john's-business.js

export class Solution {

  /**
   * business
   *
   * @param A: The prices [i]
   * @param k: 
   * @return: The ans array
   */
  business(A, k) {
    let ans = []
    let costHeap
    for (let i = 0; i < A.length; i++){
        let minCost = 0
        if (i == 0){
            costHeap = this.initMinCostHeap(A, k)
        } else {
            if (i - k > 0){
                costHeap.remove(A[i - k - 1])
            }
            if (i + k < A.length) {
                costHeap.add(A[i + k])
            }
        }
        minCost = costHeap.storage[0]

        ans.push(Math.max(A[i] - minCost, 0))
    }
    return ans
  }

  initMinCostHeap(A, k){
        let costHeap = new Heap()
        for (let j = 0; j <= k; j++){
            costHeap.add(A[j])
        }
        return costHeap
  }
}

class Heap {
    constructor(){
        this.storage = []
    }

    add(elem) {
        this.storage.push(elem)
        for (let i = this.storage.length - 1; i > -1;) {
            let parent = Math.floor((i - 1) / 2);
            
            if(parent < 0) {
                break;
            }

            if (this.storage[i] < this.storage[parent]) {
                let temp = this.storage[parent]
                this.storage[parent] = this.storage[i]
                this.storage[i] = temp
                i = parent
                continue
            }
            break;
        }
    }

    remove(elem) {
        const idx = this.storage.findIndex(val => val === elem)
        let last = this.storage.pop()
        this.storage[idx] = last;
        for (let i = idx; i < this.storage.length;) {
            let child1 = 2 * i + 1;
            let child2 = 2 * i + 2;

            let minChild = 0;
            if(child1 >= this.storage.length) {
                break;
            }
            if (child2 >= this.storage.length) {
                minChild = child1;
            } else {
                minChild = this.storage[child1] > this.storage[child2] ? child2: child1
            }

            let temp = this.storage[minChild]
            this.storage[minChild] = this.storage[i]
            this.storage[i] = temp
            i = minChild
        }
    }
}