[871] 最低加油次数

贪心算法

details

var minRefuelStops = function (target, startFuel, stations) {
    let maxHeap = new Heap();

    let refuels = 0;

    let curFuel = startFuel;

    let prevDis = 0;
    const newStation = stations.concat([[target, 0]]);

    // 遍历所有加油站和终点
    for (let i = 0; i < newStation.length; i++) {
        let [dis, fuel] = newStation[i];

        curFuel -= dis - prevDis;
        while (curFuel < 0 && maxHeap.size() > 0) {
            curFuel += maxHeap.dequeue();
            refuels++;
        }

        if (curFuel < 0) return -1;

        maxHeap.enqueue(fuel);
        prevDis = dis;
    }
    return refuels;
};

class Heap {
    constructor() {
        this.data = [];
    }
    parentIndex(i) {
        return ((i - 1) / 2) >> 0;
    }
    leftIndex(i) {
        return 2 * i + 1;
    }
    rightIndex(i) {
        return 2 * i + 2;
    }
    swap(i, j) {
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
    }
    size() {
        return this.data.length;
    }
    enqueue(val) {
        this.data.push(val);
        this.heapifyUp();
    }
    peek() {
        return this.data.at(0);
    }
    heapifyUp() {
        let i = this.size() - 1;
        let pIndex = this.parentIndex(i);
        while (pIndex >= 0 && this.data[i] > this.data[pIndex]) {
            this.swap(i, pIndex);
            i = pIndex;
            pIndex = this.parentIndex(i);
        }
    }
    dequeue() {
        if (this.size() === 0) return null;
        if (this.size() === 1) return this.data.shift();
        const root = this.data.at(0);
        this.data[0] = this.data.pop();
        this.heapifyDown();
        return root;
    }
    heapifyDown() {
        let i = 0;
        while (this.leftIndex(i) < this.size()) {
            let maxIndex = this.leftIndex(i);
            if (this.rightIndex(i) < this.size() && this.data[this.rightIndex(i)] > this.data[maxIndex]) {
                maxIndex = this.rightIndex(i);
            }

            if (this.data[i] < this.data[maxIndex]) {
                this.swap(i, maxIndex);
                i = maxIndex;
            } else {
                break;
            }
        }
    }
}