LeetCode 480.滑动窗口中位数问题代码调试求助

题目描述 #

给定整数数组nums和整数k，存在一个大小为k的滑动窗口从数组最左端移动到最右端。你只能看到窗口内的k个数字，每次窗口向右移动一位。返回原数组每个窗口的中位数数组，答案与实际值误差在10^-5以内即可被接受。

怀疑存在问题的代码片段 #

const medianSlidingWindow = (array, window) => {
    let start = 0;
    let end = window - 1;
    const min = new MinHeap(array);
    const max = new MaxHeap(array);
    const insert = (index) => {
        if(max.size === 0){
            max.push(index);
            return;
        }
        (array[index] >= max.peak) ? min.push(index) : max.push(index);
        balance();
    }
    const balance = () => {
        if(Math.abs(max.size - min.size) >= 2){
            const returned = (max.size > min.size) ? max.pop() : min.pop();
            (max.size > min.size) ? min.push(returned) : max.push(returned);
        }
    }
    const remove = (index) => {
        (max.has(index)) ? max.pop(index, true) : min.pop(index, true);
        balance();
    }
    const next = () => {
        remove(start++);
        insert(++end);
    }
    const getMedian = () => {
        if(window % 2 === 0) return (max.peak + min.peak)/2;
        return (max.size > min.size) ? max.peak : min.peak;
    }
    for(let i = 0; i <= end; i++){
        insert(i);
    }
    const ret = [];
    while(end < array.length){
        ret.push(getMedian());
        next();
    }
    return ret;
}

完整代码 #

class MaxHeap{
    #array = [];
    #size = 0;
    #reference = [];
    #map = new Map();
    constructor(reference = []){
        this.#reference = reference;
    }
    get size(){
        return this.#size;
    }
    /* Debug */
    get array(){
        return this.#array;
    }
    get peak(){
        return this.get(0);
    }
    get(index){
        if(index === null || index < 0 || index >= this.#array.length) return null;
        return this.#reference[this.#array[index]];
    }
    has(indexReference){
        return this.#map.has(indexReference);
    }
    swap(indexA, indexB){
        let temp = this.#map.get(this.#array[indexA]);
        this.#map.set(this.#array[indexA], indexB);
        this.#map.set(this.#array[indexB], temp);
        [this.#array[indexA], this.#array[indexB]] = [this.#array[indexB], this.#array[indexA]];
        
    }
    sink(index){
        let currentIndex = index;
        let greterChild;
        while((this.get(greterChild = this.get(2*currentIndex+1) >= this.get(2*currentIndex + 2) ? 2*currentIndex + 1 : 2*currentIndex + 2) ?? Number.MIN_SAFE_INTEGER) > this.get(currentIndex)){
            this.swap(currentIndex, greterChild);
            currentIndex = greterChild;
        }
    }
    bubble(index){
        let currentIndex = index;
        let parent;
        while((this.get(parent = Math.ceil((currentIndex - 2)/2)) ?? Number.MAX_SAFE_INTEGER) < this.get(currentIndex)){
            this.swap(currentIndex, parent);
            currentIndex = parent;
        }
    }
    push(...char){
        if(char[0].constructor === Array) char = char.flat();
        for(let i = 0; i < char.length; i++){
            this.#array.push(char[i]);
            this.#map.set(char[i], this.#array.length - 1)
            this.bubble(this.#array.length - 1);
            this.#size++;
        }
    }
    pop(index = 0, fromReference = false){
        const ret = (fromReference) ? index :this.#array[index];
        if(fromReference) index = this.#map.get(index);
        this.swap(index, this.#array.length - 1);
        this.#map.delete(ret);
        this.#array.pop();
        this.sink(index);
        this.#size--;
        return ret;
    }
}
class MinHeap extends MaxHeap{
    constructor(reference = []){
        super(reference);
    }
    get size(){
        return super.size;
    }
    get peak(){
        return super.peak;
    }
    /* Debug */
    get array(){
        return super.array;
    }
    bubble(index){
        let currentIndex = index;
        let parent;
        while((this.get(parent = Math.ceil((currentIndex - 2)/2)) ?? Number.MIN_SAFE_INTEGER) > this.get(currentIndex)){
            this.swap(currentIndex, parent);
            currentIndex = parent;
        }
    }
    sink(index){
        let currentIndex = index;
        let lesserChild;
        while((this.get(lesserChild = this.get(2*currentIndex+1) >= this.get(2*currentIndex + 2) ? 2*currentIndex + 2 : 2*currentIndex + 1) ?? Number.MAX_SAFE_INTEGER) < this.get(currentIndex)){
            this.swap(currentIndex, lesserChild);
            currentIndex = lesserChild;
        }
    }
}

const medianSlidingWindow = (array, window) => {
    let start = 0;
    let end = window - 1;
    const min = new MinHeap(array);
    const max = new MaxHeap(array);
    const insert = (index) => {
        if(max.size === 0){
            max.push(index);
            return;
        }
        (array[index] >= max.peak) ? min.push(index) : max.push(index);
        balance();
    }
    const balance = () => {
        if(Math.abs(max.size - min.size) >= 2){
            const returned = (max.size > min.size) ? max.pop() : min.pop();
            (max.size > min.size) ? min.push(returned) : max.push(returned);
        }
    }
    const remove = (index) => {
        (max.has(index)) ? max.pop(index, true) : min.pop(index, true);
        balance();
    }
    const next = () => {
        remove(start++);
        insert(++end);
    }
    const getMedian = () => {
        if(window % 2 === 0) return (max.peak + min.peak)/2;
        return (max.size > min.size) ? max.peak : min.peak;
    }
    for(let i = 0; i <= end; i++){
        insert(i);
    }
    const ret = [];
    while(end < array.length){
        ret.push(getMedian());
        next();
    }
    return ret;
}

问题详情 #

提交代码后在第30个测试用例返回错误答案，但单独测试该测试用例中出错的窗口时结果却正确。目前确认两个堆的平衡状态正常（一个堆的元素数量不会超过另一个堆1个以上），且堆的实现单独测试也没有问题，希望找出代码中的错误。

内容的提问来源于stack exchange，提问作者Haekal Alexander