480.滑动窗口中位数

链接：480.滑动窗口中位数
难度：Hard
标签：数组、哈希表、滑动窗口、堆（优先队列）
简介：给你一个数组 nums，有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

题解 1 - typescript

• 编辑时间：2021-02-03
• 执行用时：168ms
• 内存消耗：44MB
• 编程语言：typescript
• 解法介绍：利用队列维护。

class BestQueue {
  get len() {
    return this.queue.length;
  }
  constructor(public queue: number[]) {}
  add(val: number, l = 0, r = this.len) {
    if (l >= r) {
      this.queue.splice(l, 0, val);
    } else {
      const mid = ~~((l + r) / 2);
      const num = this.queue[mid];
      if (num > val) {
        this.add(val, l, mid);
      } else if (num < val) {
        this.add(val, mid + 1, r);
      } else {
        this.queue.splice(mid, 0, val);
      }
    }
  }
  del(val: number) {
    this.queue.splice(this.queue.indexOf(val), 1);
  }
  findMid() {
    return this.len & 1
      ? this.queue[(this.len - 1) / 2]
      : (this.queue[this.len / 2] + this.queue[this.len / 2 - 1]) / 2;
  }
}
function medianSlidingWindow(nums: number[], k: number): number[] {
  const queue = new BestQueue(nums.slice(0, k).sort((a, b) => a - b));
  const ans = [queue.findMid()];
  for (let i = k, l = nums.length; i < l; i++) {
    queue.del(nums[i - k]);
    queue.add(nums[i]);
    ans.push(queue.findMid());
  }
  return ans;
}